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.
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?