Week 10, Wednesday: Recursion

examples from last time

Recursion can be tricky to understand. The more recursive functions you write, the easier it will get. See the recursion-practice file in your inclass/w10-recursion directory for additional examples of recursive functions you can write.

Here is one from last class:

def coinflip(n):
  """flip n coins, return number of heads"""
  if n <= 0:
    return 0
  else:
    flip = randrange(2)  # 1 = Heads
    return flip + coinflip(n-1)

In the above function, I used randrange(2) to be the coinflip, and am assuming zero is Tails and one is Heads. By doing that, the variable flip can be added to coinflip(n-1) to get the total number of Heads. If that is confusing to you, here is another, more explicit way you could have written the function:

def coinflip(n):
  if n <= 0:
    return 0
  else:
    flip = choice(["Heads","Tails"])
    if flip == "Heads":
      return 1 + coinflip(n-1)
    else:
      return 0 + coinflip(n-1)

Notice that I am assuming coinflip(n-1) will work and give me back the result I want (the number of Heads from flipping n-1 coins). This is often called the leap of faith, and is sometimes the hardest part about writing a recursive function. If, however, you can make that leap, the function is much easier to understand.

Also notice that we know the answer to the base case: if zero coins are flipped, there are zero Heads. Seems trivial, but the base case is needed to stop the recursion.

If you don't see how the recursive calls to coinflip() produce the final result, try running it in the python tutor! Once you see the stack, with all of it's frames, you should see how the results of each coin flip are added together (via recursion, not a for loop!) to give the answer.

Here is another example from last class:

def count(x,L):
  """return how many of x are in L"""

  if len(L) == 0:
    return 0
  else:
    count_rest = count(x, L[1:])
    if x == L[0]:
      return 1 + count_rest
    else:
      return count_rest

In this example, I explicitly define a count_rest variable to hold the answer to the recursive calls. Once I have made that leap of faith (count(x, L[1:]) will work!), I just need to determine if the first item in the list (L[0]) is what I am looking for.

Again, for the base case, we know the answer: if there are zero items in the list, obviously, there are no x's in the list.

practice, practice, practice

See of you can write these recursive functions! Feel free to work with your neighbors. And ask lot's of questions!

 maxOfList(L)     # return the largest item in the list
 isSorted(L)      # return True if list is sorted, False if not
 isPalindrome(S)  # return True if string is a palindrome, False if not

For each of these, how do you handle the first item in the list, or the first character in the string?