The limits of recursion with Python
Recursion – a function calling itself – is a fundamental concept in functional programming. Many languages that cater to functional programming are able to recurse ad infinitum. Python is not one of those languages. You can use recursion in Python, but you have to be aware of its limits, namely that recursion incurs quite a lot of memory costs and that it cannot be used to replace iteration – a typical case when writing functional programs.
To see the limits of recursion with Python, we are going to implement the Fibonacci sequence in several ways. As a reminder, Fibonacci can be defined as follows:
Fib(0) = 0 Fib(1) = 1 Fib(n) = Fib(n -1) + Fib(n –2)
We are also computing the factorial function, but in this case only in a recursive way:
Fact(1) = 1 Fact(n) = n * Fact(n –1 )
Getting ready
Our code is available in Chapter12/Recursion.py.
How to do it...
Follow these steps to get started:
...
