- return/review Quiz 4
- lab 8 due this Saturday

Recursion is when a function calls another copy of itself to finish the work.
Some algorithms, like the merge sort (or any *divide-and-conquer* algorithms), are
more easily expressed using recursion. This week we will practice writing recursive
functions.

Obviously, if the function calls another copy of itself, the other copy may call yet *another* copy,
and so on. This leads to repetition, very similar to a loop. In fact, designed correctly,
a recursive function can simply replace a `for loop`

. So all of the functions we have
written so far (sum a list, blastoff, find the max of a list, etc) can be written using
recursion (and not using a `for`

loop or a `while`

loop).

Here is the simple `blastoff(n)`

function, to show a countdown from some number `n`

, using a `for loop`

:

```
def blastoff(n):
for i in range(n,0,-1):
print(i)
print("blastoff!")
```

Thinking *recursively*, you may notice that `blastoff(10)`

is really just this:

```
print(10)
blastoff(9)
```

And `blastoff(9)`

is this:

```
print(9)
blastoff(8)
```

And so on. The key to writing an algorithm recursively: **handle the first item or case, then
let recursion handle the rest**. For the above, given an integer `n`

, we would:

```
print(n) # take care of n
blastoff(n-1) # let recursion handle the rest
```

Also note, each subsequent call to `blastoff()`

has a smaller value of `n`

.
Eventually we will call `blastoff(2)`

, then `blastoff(1)`

, and then, finally, `blastoff(0)`

.
At that point, we want to just print "blastoff" and stop the recursion. This is formally
called the **base case**, and is usually written with an `if/else`

clause.

Here is the full recursive blastoff function:

```
def recursiveblastoff(n):
if n <= 0:
print("blastoff!")
else:
print(n)
recursiveblastoff(n-1)
```

Notice the base case stops the recursion (does not call another copy).
Also notice the non-base case (the `else`

clause) heads toward the base case
by calling another copy, but with `n-1`

as the argument.

Sometimes, to understand recursion, it helps to think about the stack frames.
If the above function were called with `n=4`

, how many frames would be put
on the stack? Try it in the python tutor!
Here is a screenshot of the stack frames,
when the recursion has reached the base case:

Here is another example, this one from mathematics: the `factorial(n)`

function is
defined as `n*n-1*n-2*...*3*2*1`

. So, for example, `factorial(5)`

is just
`5*4*3*2*1`

. Notice, however, that `factorial(5)`

*can be written* as just
`5*factorial(4)`

, since `factorial(4) = 4*3*2*1`

. If `factorial(0) = 1`

, can
you write a recursive factorial function? You can test your function against
the factorial function in the `math`

library:

```
>>> from math import factorial
>>> factorial(5)
120
>>> factorial(8)
40320
```

Note: both the factorial() and the blastoff() functions can easily be written *without*
using recursion. We are just using them as simple examples. This week we will try to write
as many recursive functions as we can, just to learn recursion and get used to thinking
recursively. Later in the week we will look at some algorithms that are more easily expressed
using recursion.

I think the hardest part about writing recursive functions is the first step, where you
need to express the problem in a recursive fashion. Try to keep the following in mind:
*handle the first case, then let recursion handle the rest*. Once you have that part
figured out, it is usually easy to write the base case. Let's try a few examples:

Given a list of numbers, `L`

, write a *recursive* function (no `for`

loops!) to
sum the list and return the result.

The first step is usually the hardest...the sum of a list is just `L[0]`

+ the sum of
the rest of the list. Using python slicing, it is easy to grab *the rest of the list*: `L[1:]`

.
If `sum(L)`

calls `sum(L[1:])`

, what is the base case we are heading toward? And if we
reach the base case, what should the function return?

Given a positive integer `n`

, flip a coin `n`

times and return the number of heads flipped.
Write a recursive `coinflip(n)`

function (again, no `for`

loops!).

Note that `n`

flips is just one coinflip plus `n-1`

more flips. So our function, in the
non-base case, needs to flip 1 coin, figure out if it was heads or tails, then let
recursion flip the other `n-1`

times, add those to the result of the first flip, and
return the full result.

Each subsequent call to `coinflip()`

has one lower value of `n`

, so what is the base
case?

Given a list of numbers, `L`

, and a value, `x`

, write a *recursive* function to
count how many of `x`

are in `L`

. For example, calling `count(range(10), 99)`

would
return `0`

, and `count([1,2,8,2,2], 2)`

would return `3`

.

Again, handle the first item in the list, `L[0]`

, then let recursion handle the rest of the list (`L[1:]`

).