We talked in class about how a recursive function is a function that calls itself from within itself. This might seem like a strange idea at first, but it will allow us to write very elegant code to do complicated things that are difficult to do with loops.

A Warmup Example

To start off with an example, let's consider the function

\[ h(x) = \left\{ \begin{array}{cc} h(x-7) + 1 & x > 5 \\ x & 0 \leq x \leq 5 \\ h(x+3) & x < 0 \end{array} \right\} \]

If we ask for h(11), we actually have to compute h(6) first. But then to compute h(6), we actually have to compute h(-1) first. But then to compute h(-1), we have to compute h(2) first. Then, finally, it stops, and we find h(2) = 2, and we can substitute in the results all the way back up to h(11). The diagram below shows this

Below is C++ code to compute this

Note that the middle if statement is called the stopping condition; this is where we return something directly instead of a recursive call. Code must have a stopping condition, or we'll end up with infinite recursion.

Below is some fancier code that keeps track of the depth of the recursion, or how many recursive calls we've made to get to the point we are at. I print out as many tabs as there are depth to help format the recursive calls to show what happens:

For example, if we call h(13, 0) (starting off at a depth of 0), we get the following output

Actually, this is a form of what's known of as tail recursion, where we make exactly one recursive call per function call if we make a recursive call, and once we reach the stopping condition, we back all the way back up. The video below shows a physical example of tail recursion in real life with bricks

---

The Factorial Function

A famous example of a tail recursive function is the factorial function

\[ N! = N (N-1) (N-2) ... 1\]

This is an extremely important example in computer science, because it describes the complexity of algorithms that consider all possible shuffles over a set with N elements. Defined recursively, the factorial is written as

\[ \text{fac}(N) = \left\{ \begin{array}{cc} N \times \text{fac}(N-1) & N > 1 \\ 1 & N = 1\end{array} \right\} \]

Note the stopping condition at N = 1 (it would continue infinitely without this).

Below is a recursive implementation of this function

If we call this on N = 1, 2, ..., 10, we get 1 2 6 24 120 720 5040 40320 362880 3628800, so we can see how quickly this function grows.

As a side note, since this is tail recursion, we can implement it with a loop

But note how in the recursive version, we didn't need a loop at all!

---

The Fibonacci Sequence And Branching in Recursion

Up to this point, we could do everything with loops, so why introduce this additional confusion? Well, recursion gives us a way to generalize loop structures by branching. As an example, let's consider the Fibonacci sequence, of which the first 10 numbers are

1 1 2 3 5 8 13 21 34 55 89

If we look at this closely, we realize the rule is that each number is the sum of the two numbers that come before it. Written recursively, we can say

\[ \text{fib}(N) = \left\{ \begin{array}{cc} \text{fib}(N-1) + \text{fib}(N-2) & N > 2 \\ 1 & N = 1, 2\end{array} \right\} \]

Note that since we actually need the previous two terms, we actually need two stopping conditions; one for N = 1 and one for N = 2.

Below is code to implement this

Let's compare the recursive calls between fib and fac. The diagram below compares fib(4) to fac(5)

With tail recursion, we go down in a line, while with branching out to two recursive calls, we quickly double the number of recursive calls we make. This means that the number of recursive calls we make for fib(N) grows as 2^N with N, which blows up very quickly! There's got to be a better way!

---

Memoization Using Maps

Part of the problem with the way we setup the Fibonacci function above is that we have overlapping subproblems everywhere. For example, to compute fib(5), we need to compute fib(4) first, then fib(3). But in the process of computing fib(4), we compute fib(3). So if we can remember fib(3), we won't have to repeat the work when we go to compute it later, and we can just look it up! The picture below shows how much we can cut out doing this:

The process of remembering the result of certain inputs to recursive functions and recalling them later is known as memoization. An ideal data structure for this is a map, where the key is the input the function, and the associated value is what the function returns at that input.

The code below shows how to use memoization for Fibonacci

This cuts down the recursive calls to ~2N instead of 2^N, which is an enormous gain in efficiency!