Recursion

0. Learning objectives

As we mentioned, on of the main goals of computer is to automate repetitive tasks. Imperative programming, where we achieve repetition using loops, is one of the programming approaches used to achieve this goal. An alternative approach is to use functions and conditionals to write recursive functions, which is an example of functional programming. Combining conditionals with our knowledge of functions will allow us to repeat calculations, and for some problems, the solutions will be more elegant and intuitive than similar solutions using loops.

1. Recursion

Recursion is a programming paradigm where a computational problem is solved by defining it in terms of a simpler version of itself. Let's look at an example illustrating the main idea behind it.

1.1. The main idea of recursion

Imagine you just arrived at the dining hall, and there is a huge line to get curly fries... and you are the last one. There are way too many people in line for you to count them all, so you tap the person in front of you on the shoulder and ask them how many people are ahead of them. Whatever number they say, you can just add 1 to get the total number of people in front of you. But how can they figure out home many people are in line in front of them? They can follow the same idea: they ask the person in front of them how many people are ahead of them and add 1 to the result. Everybody is too lazy to count the entire line so let's suppose this continues until the person at the start of the line is reached (yes, you can assume the line does not move in the meantime). How many people are in front of this person? None! So they turn around and answer "Nobody is in front of me". The second person in line then adds 1 and tells the third person in line "There is one in front of me". The third person in line then adds 1 and tells the fourth person in line that there are 2 people ahead of them. This continues until it finally gets back to you at which point you finally know the total number of people ahead of you in the line (and having found out the actual number, decide to go get a salad instead... nobody is ever in that line...).

Click on in the demo on the right to see how this works.



This is main idea of recursion: keep repeating the same set of instructions (calling the same function) until we reach some base case. The base case consists of a problem we know how to solve, so we solve it and then return the solution to the previous call (in this case, the base case happens to the first person in the line who doesn't have anybody in front of them. This is very easy to solve. "How many people are in front of you?" - "zero!"). Otherwise, we keep calling the function recursively: we need to make sure that the inputs to our recursive function calls are getting closer and closer to our base case (in our example, at every step, we are getting closer and closer to the beginning of the line). Otherwise, the program would run forever! (You would really never know how many people are in the line in front of you, if you keep asking yourself that question instead of the question moving forward along the line).

1.2 Ingredients for writing a recursive function

The main ingredients we need for writing a recursive function are a base case and a recursive step. At the beginning of our recursion, the problem is too difficult to solve, but we can break it up into a problem(s) we know how to solve and use that result to solve our current problem. The outline of a recursive function is shown on the right, and the ingredients are described below. Keep in mind that, depending on the type of problem you are trying to solve, functions might differ from this template, but they will definitely have:

  • Base case: represents a problem you know how to solve.
  • Recursive step: represents a problem you don't know exactly how to solve, however you can break it up into smaller problems that you know how to solve, and then use those results to solve your current problem.

In the curly fries example, the "big problem" was figuring out how many people are in front of us. Since we couldn't solve this directly, we broke it up into a "smaller problem", in which we asked the person in front of us how many people are in front of them and then added 1 to the result.

The example above contains two examples of the possible form for a recursive function. We are calling the function passing some input as parameter on which we want to perform some computation. However, we can't directly perform this computation on this input, so we call our recursive_function (yup, the same one) with a smaller version of our problem (usually a smaller version of input) until we finally reach the base_case. You can think this as some conditional expression applied to input that returns either True or False. If the condition is True then we have reached our base case, otherwise we have to keep calling ourselves with a smaller version of the problem. Once we reach the base case, we can know we can solve the problem (nobody is in front of us in the line) and we can return this result. This returned result will be sent back to the previous call of our function which will perform some computation with it and then pass the result to the previous call, and so on, until we finally arrive to the original call with the original input and we can finally provide the solution to the original problem.

Check your understanding by determining if both versions (switch the version by clicking on the tabs) do the same thing.

This was more of an exercise in the syntax for writing conditionals and functions. In fact, yes, both versions do exactly the same thing. In Version 1, the recursive step is written in the else portion, which is never reached if the base case is reached. In Version 2, we automatically return from the function after doing some computation for the base case. So the stuff on Line 14 are not reached if the base case is reached (but they are reached for functions that call the base case).

Examples

Example 0. Arithmetic series

Remember the iteration example where we computed the sum of the first $n$ natural numbers? Here is a possible recursive solution to the problem.

Example 1: power

Let's write a recursive function to compute the value of some input number $x$ raised to te power of an integer $p$, denoted by $x^p$. Yes, I know that Python can do this with x ** p but let's write a recursive function to do this. For an integer $p$, we can write out $x^p$ as

$$x^p = \underbrace{x \cdot x \cdot x\cdot \ldots \cdot x}_{\mbox{$p$ times}} = x \cdot (\underbrace{x \cdot x \cdot \ldots \cdot x)}_{\mbox{$p-1$ times}} = x\cdot x^{p-1}$$

So we have broken up our problem (which we can't solve directly) into a smaller problem and then use the solution to that smaller problem to compute the solution to our problem using the multiplication operator to combine the two. Eventually, as we keep decrementing (subtracting 1 from $p$), we will reach $p = 0$. What's $x^0$? It's just 1! This is our base case.

Try completing the power function below. Check that your function works correctly by calling power(2, 4) (you can use the print function in the code) and making sure you get 16.

Example 2: factorial

Let's do another math-y example, this time with the factorial, represented with an exclamation point. Recall that $5! = 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1$. Observe that $5! = 5 \cdot 4!$ and $4! = 4 \cdot 3!$. Hmm, this sounds pretty recursivey. So in order to compute $5!$, we can just multiply $5$ times whatever we get from $4!$, and then keep doing that until we get to our base case. What is our base case? Well when we get to $1$, then $1! = 1$ (in fact, $0!$ is also equal to $1$).

Your turn!

Example 3: let's count the spaces in a string!

Notice how the recursive case keeps making the problem smaller until we reach the base case, and how the solution (returned values) of the smaller problems are combined (added) to provide the solution for the larger (original) problem.

An iterative solution is provided at the bottom so that you can compare the two solutions.

Example 4: counting vowels

Let's imagine that we want to write a function that will count the vowels in a given string. We'll start by just counting the lower-case ones, then we'll see how Python can make our life easier and add the upper-case ones. Because we are still talking about recursion, we want to solve this problem using this particular approach. So, where do we start? Remember that we have to find two things:

So, where do we start? What is the trivial case where, without doing any computation, you can with certainty say that there are no vowels in a string? The empty string! If there is no string, there are going to be no vowels! Great! That's our base case. What about the recursive part? If the string is not empty, we might want to start looking at the first character and check if it is a vowel. We now have to possible outcomes: it is a vowel, it is not a vowel. In either cases, we are not done... there might be more string to look at. In other words, once we have decided if the first character is a vowel or not, we still need to look if there are vowels in the rest of the string. Do we have a function that tells us how many vowels are in a string? YES! It's the function we are writing! In recursion, you have to trust yourself and believe that the function you are writing will do the job you are writing it to do!

So, try to come up with the function in the code editor below. Then you can look at the solution. There are two solutions, the second uses a new Python operator the in operator. This operator will check if the operand on the left can be found within the operand on the right (typically a collection of element) and it will return True, if it can be found and False otherwise. Here are few examples: 

'a' in 'recursion'    # Will return False because there is no 'a' in 'recursion'
'e' in 'recursion'    # Will return True
'cur' in 'recursion'  # Will return True
'cor' in 'recursion'  # Will return False

The in operator works with many different types of collections and we will see more example but, for now, you can think of it as a nice way to check if a letter is inside a collection of letters (a string).

Example 5: palindrome tester

Palindromes are string that can reads the same forward and backward. For example 'ada', 'step on no pets', etc.

Your challenge is to write a recursive function that will check if a string is palindrome and return True if it is andFalse if it isn't (you can consider a single character string and the empty string to be palindrome). Once again, before start coding, think about what it means to be palindrome. How could you state the problem in a recursive way? How could you do a check to that brings you closer to verify if the string is palindrome? What would be a good base case?

Example 6: the containers problem

Here is a problem that might sound familiar. You are given a certain amount of cups of a fluid and you have at your disposal containers of the following sizes: gallon (16 cups), quart (4 cups), pint(2 cups), and cups. Using all the amount of fluid that is given to you, fill up the least amount of containers. The only constraint is that all containers have to be completely filled (e.g., you cannot have a one gallon container half full).

Can you think how you can solve this using recursion? Hint: there are several recursive cases!

Example 7: the "go back" function

Let's try now to get a feel for the path Python takes through a program. Consider the following recursive function that hopefully clarifies the path a recursive function call takes.

The go_back function has an integer n as parameter. The function prints stop! when we reach the base case. Otherwise, in the recursive case, we print go (along with the current value of n) right before we call go_back recursively with an input of n - 1, making the "problem" smaller. Once this recursive call returns, we print back followed by the local value of n.

What do you think is going to be the result of running go_back(5). Think before you run the code!

2. Stack diagrams revisited

The go_back function in the last exercise revealed the "path" a recursive function takes after it is called, which can be tricky to visualize. One useful method for visualizing the path your program takes is to use the stack diagram we described when talking about functions and the scope of variables. If you remember, a stack diagram is composed of stack frames, each representing the scope of a particular function call. You can draw out each frame as a box (review the variable scope section in the function module and the examples we discussed). Inside each box, you should put a title for the box which includes the function name and values of the parameters (if any), local variables (if any), as well as return value (if any). Now your job is to "be the interpreter", in other words, do the calculations Python would do for you, calculating intermediate variables and then writing out call the "calls" to other functions. Whenever you call another function (even if it is the same function as in recursion), create a new frame! You should also draw an arrow between the frames each time

At the end of the day, you should have two arrows between all the frames: one when you go down the functions calls, and one when go back up.

Have a look at the following demo on for the go_back function. This demo describes the steps you would take to draw a stack diagram for the initial input of go_back(5).

Click on the to take a single "step" through the execution of the program. Notice which line is currently being executed in the editor on the left.



Go through these examples in Thonny (you can copy the code from here and paste it), and use the step into function of the debugger and observe carefully what happens when you call a function calls itself in the recursive case. The execution of the current function is suspended since we are waiting for a return value from out new function call. Thonny opens a new window where it lists the scope of the "new" function call with the new parameter values as variables at the bottom. This window represents a new stack frame. Each function call will open a new frame until we reach the base case at which point we are going to start returning back from each function call and closing frame after frame.

Technically speaking, there is also a frame for the "main" portion of the script.

3. The "dark side" of recursion

3.1. Fibonacci numbers

In spring time, bunnies are starting to take over... Fibonacci (1200 ca.) studied an idealized model for bunny population growth. Assume that we start with two baby bunnies. Bunnies mature into adult after 1 month at which point they breed a new pair of baby bunnies (this is an assumption in our idealized model). So at the beginning, we have no bunnies, but then after 1 month we have a pair of baby bunnies. The following month, these baby bunnies have matured into a pair of adult bunnies. The month after that, these adults bunnies had a new pair of baby bunnies, which then mature into a new pair of adult bunnies for the following month. Thus, every month, any existing pair of adult bunnies had a new pair of baby bunnies and any baby bunnys at the start of the month are now fully grown adult bunnies... that's a lot of fluffiness...

We can express the total number of bunny pairs $F(n)$ in terms of the month $n$. Our model is therefore

$$ F(n) = F(n-1) + F(n-2) \quad \mbox{for } n \ge 2,\quad \mbox{ and } \quad F(0) = 0,\ F(1) = 1. $$

This is the Fibonacci sequence! The $n$-th Fibonacci number is called $F(n)$, which can be expressed as the sum of the $(n-1)$-th Fibonacci number plus the $(n-2)$-th Fibonacci number.

Using your now awesome skills, write a recursive function fib(n) which computes the $n$-th Fibonacci number in the sequence. How many base cases should you have? (at the beginning there are no bunnies, after a month we have one pair of bunnies). Ensure that your function correctly computes $F(10) = 55$.

Fibonacci sequences appear in various patterns in nature, including branching in trees, fruitlets of a pineapple and the flowering of the leaves of artichokes and pinecones to name a few. But the recursive solution hold a dark secret...

Try to run fib(20), and then run fib(30) (try it in Thonny). You can even be ambitious and run fib(40) (don't!). What do you notice? The higher n, the longer it gets. Actually just going up by one it makes a huge difference when n starts getting large! I don't recommend trying fib(40) or you'll be waiting a loooong time!

What is going on?

The reason that our fib(n) function is slow is because it has to recompute many values that have already been computed over and over again. For example, let's expand fib(5):

Notice how many times we are recomputing $F(n-2)$ since $F(n-1)$ depends on it, and each time our recursive function has to go back all the way to the base cases. If you think about it, every time you move down a level in this upside-down tree, we are doubling the number of computation we need to do: we need two to calculate the root at the top (our fib(5), then we need 4 to calculate these two, and so on. (If you were to start from higher numbers you would see that pattern pretty clearly before getting down to the leafs. If you think about it for a second, if we doubling at every level and there are n levels (look all the way to the left, the longest path and imagine a much larger tree starting from 10, or 20), then we need evaluate our fib(n) function $2^{n}$ times! And that is a number that gets big pretty quickly. That's the reason why, when we get around n = 38, the evaluation start getting longer and longer and, at every step, twice as long! This gives you an idea of what, in Computer Science, we call the complexity of an algorithm. We will talk more about complexity, but with this example, you can start getting a feeling that there might be different way of solving some taking longer than other but that might have other advantages. The basic idea is that there is no free lunch! (Rule 1: no free lunch! Rule 2: Physics is not an opinion!)

There are few ways around this:

We will see how to do the former in a few weeks, but here comes an example of the latter.

We can make the problem less computationally complex, while remaining recursive, by keeping track of how many Fibonacci numbers we still need to compute in order to compute the $n$-th Fibonacci number, starting from $F(0)$. For example, if we want to compute $F(5)$, then we know that $F(0) = 0$ and $F(1) = 1$, so we need to compute $F(2)$, $F(3)$ and $F(4)$ to compute $F(5)$. This means that we have 3 Fibonacci numbers remaining to be computed. Whenever we want to compute those remaining Fibonacci numbers, they will require one less Fibonacci number to be computed (i.e. remaining - 1). Check out the solution to this problem below. This is a pretty confusing solution to the Fibonacci number calculation, but it now allows you to compute fib(40) in an instant (which we weren't able to do before). I suggest printing out the values (uncomment Line 4) to see the order in which fib_helper is called, and all the values for the previous, current and remaining Fibonacci numbers. Although this solution is much more efficient, it's much harder to read and understand.

So, why use recursion at all?

Remember that the purpose of programming languages and constructs is to communicate. We saw that they are a formal way to communicate behavior. The formalization, allows the computer to interpret them but the reason why they exists is for the humans! You might remember that computers only care about zeros and ones... they do not care about recursions or ifs. Those constructs are there for us to communicate to other humans (and our future-selves). Recursive solution looks very direct, like our informal description: "if you find a space it is one, and then you add the spaces that you find in the rest of the string". We are pretty much describing how we are going to solve the problem. The hardest part is describing the problem in such a way that we can decompose it and identify a base case and a recursive case where we can solve a little part of the problem and combine it with a smaller version of the same problem. Sometime problems that we need to tackle are recursive in nature (e.g., traversing the file system: finding all your folders and files) in these cases recursion lands itself beautifully to solve the problem. But sometimes, the straightforward and elegant way to solve the problem with recursion might increase the computational complexity (costs) of our algorithm. Once again, there is no free lunch and the goal is to use the best tool for the job at hand, where "best" might be a compromise between complexity and easiness to understand.