# 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:
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?