Getting Past the Recursion Issues For Factorial and Fibonacci in Python, Using Recursion

The most commonly used examples for recursion in programming are the functions to work out the factorial of a number and to work out any number in the Fibonacci sequence. Recursion is when a function calls itself over and over again.

I'll keep this blog post brief, so I won't go into the details of what these functions do and how. The recursion versions for these functions in Python are shown below. The factorial function first:

>>> def factorial(n):
...    if n == 0:
...        return 1
...    return n * factorial(n-1)
...

And the Fibonacci sequence next:

>>> def fibonacci(n):
...    if n == 1:
...        return 0
...    if n == 2:
...        return 1
...    return fibonacci(n-1) + fibonacci(n-2)
...

These examples are often used to show some of the problems with recursion. Let's try the factorial one first:

>>> factorial(10)
3628800
>>> factorial(20)
2432902008176640000
>>> factorial(1000)
Traceback (most recent call last):
  File "<input>", line 1, in <module>
  File "<input>", line 4, in factorial
  File "<input>", line 4, in factorial
  File "<input>", line 4, in factorial
  [Previous line repeated 986 more times]
  File "<input>", line 2, in factorial
RecursionError: maximum recursion depth exceeded in comparison

This works fine for relatively small numbers but beyond a certain point, there are too many Russian dolls nested inside each other. You hit a recursion limit. You cannot use this function to work out the value for large factorials.

The problem with the Fibonacci sequence is different:

>>> fibonacci(10)
34
>>> fibonacci(20)
4181
>>> fibonacci(30)
514229
>>> fibonacci(40)
63245986
>>> fibonacci(100)

When you run the above functions, you'll notice that each one will take a longer time to run than the previous one. Finding the 40th Fibonacci number is likely to take several seconds or more, depending on what computer you're using. You'll probably give up rather than wait for the 100th number. And don't even think of trying fibonacci(1000).

One solution to this problem is to avoid recursion altogether. You can use a for loop in both instances and this will solve both problems.

However, I'll talk about another solution here: memoisation. The problem with recursion is that there's a lot of wasted computational effort. If you work out factorial(10), the function will have to work out factorial(9), factorial(8), and so on all the way to factorial(0). You could skip 0 and 1, but you can't skip the rest.

Then, if you want to work out factorial(11), your program will need to go through all of the same process, plus factorial(10) too. But it had already worked out the value of all the factorials from 9 to 0. What if your program could remember the value for factorial(10) so that when you run factorial(11), all it needs to do is multiply the memorised value of factorial(10) by 11?

Let's see how we can do this. I'll be using a function from Python 3.9 here, although there's a similar version in older Python versions:

>>> import functools
>>> factorial = functools.cache(factorial)
>>> factorial(400)
64034522846623895262347970...  # not showing all digits here
>>> factorial(800)
77105301133538600414463939...  # not showing all digits here
>> factorial(1000)
40238726007709377354370243...  # not showing all digits here

Voilà. You're using the function cache() from the module functools. This function wraps the original function and adds some extra functionality to it. In this case it adds the functionality to memorise the values for any function call with a given argument.

You still can't run factorial(1000) right away. But if you run factorial(400), then the value of this function will be stored in memory. So when you run factorial(800), the function only needs to work out from 799 to 401, since it already knows the answer to factorial(400). Then you can take the next step to factorial(1000).

Let's try the same trick on the Fibonacci numbers function:

>>> fibonacci = functools.cache(fibonacci)
>>> fibonacci(100)
218922995834555169026

>>> fibonacci(500)
86168291600238450732788312165664788095941068326060883324529903470149056115823592713458328176574447204501

>>> fibonacci(800)
42819299437432302617632053522679588759544125417235071019025069011950982099745888354964809941468470253059003158607459662907055750510443512830937550167717484757372564701

>>> fibonacci(1000)
26863810024485359386146727202142923967616609318986952340123175997617981700247881689338369654483356564191827856161443356312976673642210350324634850410377680367334151172899169723197082763985615764450078474174626

In the original version, even the 100th term would have taken too long to compute, never mind the 1000th term. But since the program is remembering the values of all previous function calls and using them when needed, the impossible now becomes possible.

This technique can come is very handy in programs where you need to call the same function repeatedly, possibly with similar values, and the function takes time to compute.

Have fun experimenting with memoisation.

Before you go, you may enjoy reading about Monty and the White Room analogy that explains what really happens when a computer program runs.

Enjoyed this and want to learn more Python for free? Check out our sister site The Python Coding Book, for in-depth guides on all things Python, or follow us on Twitter @codetoday_ and @s_gruppetta_ct