# Week 4 - Recursion and Tree Recursion

## Table of Contents

## Recursion

It’s kinda like magic, but once you get it, it’s pretty cool.

– some 61a student, probably

In essence, a *recursive function* is a function that calls itself at some point. It’s not special syntax within Python. For those who have prior experience with *mathematical induction*, it has many similarities.

### Factorial

Let’s take the example of computing a factorial, the product of all positive integers less than or equal to n. ^{1}

A simple way to think about `factorial(n)`

is as follows:

- If \( n \leq 1 \), then \( n! \rightarrow 1 \)
- Otherwise, \( n! \rightarrow n * (n-1)! \)

Let’s transform this into Python:

```
def factorial(n):
if n <= 1:
return 1
else:
return n * factorial(n-1)
```

Let’s write this to be more Pythonic by dropping the `else`

and deintenting the inner block:

```
def factorial(n):
if n <= 1:
return 1
return n * factorial(n-1)
```

This example is recursive! Our *base case* is the *simplest problem*, when `factorial(n)`

is a known value. In this case, our base case is when `n <= 1`

. Our recursion is a known reduction of the problem, where `factorial(n)`

is the same problem as the *easier problem* `n * factorial(n-1)`

. This way, we are *reducing our problem into smaller and smaller problems until we get to a known state*.

##
### For Those Familiar With Induction

Proof by induction is logically very similar to recursion.

In induction, a typical proof for a mathematical formula goes like:

- Prove base case
- Assume the formula holds for \( k \), and prove that the formula holds for \( k+1 \).

The proof works because:

- For some base case, we know the formula to be true
- For some unknown problem of size \( k \), we have shown the formula to be reduceable to \( k - 1 \).

In recursion, the thinking maps to the above concepts:

- We want to find a base case that is a
*known state*for some function. - For a problem \( k \) with no immediately known solution, we find a reduction to a size of \( k - 1 \).

## Tree Recursion

Recursion on trees?

– the same 61a student, probably

Contrary to its name, tree recursion isn’t recursion on trees. ^{2} Instead, it refers to the recursion problems that require multiple calls to a function to break down the recurrence.

### Fibonacci

Let’s take a look at the fibonacci sequence, a sequence of numbers where each number in the sequence is the sum of the two prior to it. More formally,

\[ F_n = \begin{cases} 1, & n = 0, 1 \\[1ex] F_{n-1} + F_{n-2}, & \text{otherwise} \\[2ex] \end{cases} \]

We can transform this definition into code. We have the cases

- If
`n == 0 or n == 1`

, then`fibonacci(n) -> 1`

- Otherwise, we want
`fibonacci(n-1) + fibonacci(n-2)`

In code:

```
def fibonacci(n):
if n == 0 or n == 1:
return 1
return fibonacci(n-1) + fibonacci(n-2)
```

Note that the major difference between this problem and the prior factorial problem is in the recurrence: Fibonacci requires *two* calls to fibonacci to solve, whereas factorial requires only 1. If we draw out the calls, it looks like a tree (hence the name *tree recursion*).

## Tips For Thinking Recursively

Recursion finally makes sense!

– the same 61a student :’)

- In some cases, finding the recurrence relation will be easier. In other cases, defining the base cases will be.
- Recurrence relation:
- Think about
*what the problem is trying to calculate*, and how that can be broken down into smaller versions of the same problem. In other words, if we have some \( f(k) \), think about how that can be broken down to some other \( f(k’) \), where \( k’ < k \)

- Think about
- Base cases:
- Think about
*what the smallest version of the problem is*. In the examples above, it’s the smallest,*trivial*versions of the problem. This is usually some case like \( f(0) \), \( f(1) \), or something similar.

- Think about