In order to understand Recursion…

A cool representation of infinite recursion

When I was asked during my studies at Holberton to explain recursion in a blog post, I was told that images are worth 1500 words. This statement is often true but I find recursion to be one of the cases where it actually doesn’t really apply. Indeed There are a lot of really cool images about recursion but they all have one common flaw. They almost always portray infinite recursion, like the one above. Therefore I much prefer the saying:

“In order to understand recursion, you must understand recursion”

It says it all. It is recursive (repeats itself indefinitely), but if you actually understand recursion you can break from the recursion, and that’s the beauty of it!

Indeed in computer science we talk about recursion in the case of functions that call themselves. By design a function that calls itself will do it forever unless you can find a way to break the circle. There would be no point to recursion if there wasn’t a way to stop it. In order to break a recursive pattern you need what’s called a base case (at list one) also called a breaking condition.

Let’s look at a very simple example in python:

1 def foo():
2     print('In order to understand recursion...')
3     return foo()
4
5 foo()

If you run the above you’ll get something as the below output in your console:

In order to understand recursion...
In order to understand recursion...
In order to understand recursion...
In order to understand recursion...
In order to understand recursion...
Traceback (most recent call last):
  File "main.py", line 5, in <module>
    foo()
  File "main.py", line 3, in foo
    return foo()
  File "main.py", line 3, in foo
    return foo()
  File "main.py", line 3, in foo
    return foo()
  [Previous line repeated 992 more times]
  File "main.py", line 2, in foo
    print("In order to understand recursion...")
RecursionError: maximum recursion depth exceeded while calling a Python object

Of course you get many more statement printed before the error message. The above just displays the end of the recursion or more precisely the moment when the computer ran out of memory because it called the function foo() too many times. We’ll talk about that latter but basically it put too many function calls on the stack. Look carefully at the last line highlighted in bold. This is the python interpreter telling us we’ve ran out of memory.

So we need a condition to get out of the recursion before we run out of memory.

1 def foo(count):
2     if count == 10:
3         print('Ending recursion')
4         return
5     print("In order to understand recursion...")
6     return foo(count + 1)
7
8 foo(0)

And this time we get the following output with no error message:

In order to understand recursion...
In order to understand recursion...
In order to understand recursion...
In order to understand recursion...
In order to understand recursion...
In order to understand recursion...
In order to understand recursion...
In order to understand recursion...
In order to understand recursion...
In order to understand recursion...
Ending recursion

Now every time we call foo() we call it with a different value. First 0 on line 8, like so foo(0); and then we add 1 to count on line 6 and call foo(0 + 1). At he next recursion, it happens all over again, we call foo(1 + 1) . Note that because we are calling foo() over and over again we can’t return from the function. We are stuck in the infinite recursion, at list until we reach our breaking condition. This happens when we call foo(9 + 1) . Now count is worth 10 therefore we branch out at line 2 because the condition is satisfied as count is indeed equal to 10. We print Ending recursion and return from the function for the first time. This will release all the other function calls that were suspended up until this point. This is the tricky bit to understand but we’ll take another example to explore this mechanism…

Every time you call a function it goes onto the stack until it is returned. In the case of recursion since you can be calling a function a bunch of times before one call returns something the function calls pile up on the stack.

Let’s look at another example to understand what’s going on:

1 def pow_recursion(num, exp):
2     if exp == 0:
3         return 1
4     if exp < 0:
5         return pow_recursion(num, exp + 1) / num
6     return pow_recursion(num, exp - 1) * num
7
8 print(pow_recursion(2, 4))

Please note that lines 4 and 5 have been added for completeness sake as we won’t be using that condition with the given example. So what happens here? First we call print() so print() goes onto the stack. But print() call pow_recursion(), so pow_recursion() goes onto the stack as well (on top of print()). But then pow_recursion() calls itself 3 more times before meeting the breaking condition. Therefore pow_recursion() goes onto the stack 3 more times as exemplified by the below drawing:

Then the last call to pow_recursion() is pow_recursion(2, 0) * 2 which triggers the breaking condition as exp is now 0 and returns 1 (line 2). The recursion is broken and the stack pile is decreased by one. Now, in a reverse motion, all the functions can return as you can see below:

This diagram allows to understand what is happening into more details:

Every time we call pow_recursion() we decrease the value of exp by 1 until it eventually gets down to 0 and as we know n⁰ is always 1. Therefore we can return 1. The current execution of pow_recursion() is waiting into the call stack to finish its execution and return. There is a pending multiplication * 2 just seating there and waiting for a value to finish its computation. Finally the returned 1 is multiplied by 2 and the function can return a result to the above function (below if we look at the stack diagram). The returned value from each function stuck on the stack trickles down to the bottom of the stack multiplying the result by 2 each time a function returns. At the same time the function is removed from the stack and the memory allocated freed. In the end it is as if we had done 1 * 2 * 2 * 2 * 2 which of course is the same as 2⁴ also know as 16!

Recursion is a hard concept to grasp and can get extremely tricky when you get into more complicated functions. It’s often hard to identify the breaking condition and call the function recursively at the right moment. always try to follow the execution of the code to understand what part of the code is about to be processed. it’s always a good idea to do so but it’s extremely important when playing with recursive functions.

As a final note, and the attempt to explain recursion with one simple image I wouldn’t pick a cool one with insane patterns repeating into oblivion but this one:

The best picture to explain recursion in my humble opinion!

Indeed, you start from outside the trampoline (your first call to the recursive function), you jump for a while (endlessly if you have an endless amount of energy) and when you lose momentum you stop (base case) and walk away from the trampoline… It is the ‘how you walk away part’ that is hard to understand but if you do, and I hope this image will help you like it did me, you will on your way to understand recursion. Until you do, remember…

“In order to understand recursion, you must understand recursion”