CSC 15 Lab 10: Recursion


1. The following non-recursive program computes the gcd of two numbers a,b

def gcd(a,b): # returns the gcd of integers a and b
  while a!=0:
    a,b = b%a, a   # assign a to b%a, b to a simultaneously
  #
  return b
#

Write a recursive version of this function without using a while loop.
Make sure that it also compute the gcd correctly (e.g, gcd(12,8)==4,
gcd(9,18)==9 etc).

1b. Do you expect this recursive function to have the same problems as
the bad examples of recursion (fibonacci and factorial) that we saw?
Explain why or why not.


###########
2. The "powerset" of a set is the set of all subsets of that set. Using
lists to represent sets, the powerset of [1,2,3] consists of 
[ [], [1], [2], [3], [1,2], [1,3], [2,3], [1,2,3] ]

Duplicates and order don't matter when we use lists to represent sets, so
[2,3] and [3,2,3] represent the same set.  

Write a function to find the powerset of any set (you may assume that the
list representing the set contains no duplicates).

Hint 1: the powerset of a set of n elements has 2**n subsets, so your
program can't possibly be very fast (it's O(2**n))

Hint 2: look at the function that computes the set of all permutations of
a list.


##########
3. Study the provided examples of recursion. Pay attention
especially to the "deepcopy" function that copies nested lists.
Also study the function that finds the depth of a nested list

3.  A list in Python can contain nested lists.  For example, with

  A = [2,[3,4],[[[5]]], [[2,7],[5,[6]]]]

A[0] is 2, A[1] is [3,4], A[2] is [[[5]]].  A[1][0] is the first element
of A[1], namely 3.  

You can determine if something is a list using the 'isinstance' predicate.
For example, isinstance([1,2],list) returns True and isinstance(4,list)
returns False.  Another way to determine if something is a list is to
write type(A)==type([]), which evaluates to true if A is a list.

Write a function to "flatten" a possibly-nested list such as A above
into a one-level list.  For example, flatten(A) should return the list

[2,3,4,5,2,7,5,6]

and flatten([2,[4,5,6,[7]]]) will return [2,4,5,6,7], etc ..

Hint: think recursively.  the program shouldn't be long.

Remember also: 
   A.append(x) adds new element x destructively to A.
   A = A+B  : appends two *lists* A and B:  [1,2] + [3,4] == [1,2,3,4].

   Careful: if A and B are both lists, then A.append(B) will create a
list within a list: [1,2].append([3,4]) creates [1,2,[3,4]].  append
and + work very differently.