The concept of recursion, which in the simplest definition is that a function calls itself, is widely applied in the programming space as it helps to break down bigger complex problems into smaller subproblems, which could be solved more easily and whose answers could be combined together to give the solution to the bigger problem. One of the most commonly seen examples for recursion function is to calculate the factorial of a number.
How would you write such function in Python? It could be as simple as these three lines:
This is a recursive call and if we look closely at how computer handles recursion in more details, we know that for each recursive call a stack will be created and pushed in the memory. This stack contains all the pertinent information including the parameter values for the function. When the function terminates (i.e. the base case is called), the information is popped out of the stack and each value within the call returned, and eventually the final value returned, as illustrated in this diagram:
There is a slight complexity involved here as our memory is limited — we do not have unlimited resources so if we are triggering a huge number of recursive calls, the stack depth becomes very big and we could hit the maximum of the stack space. For example, we will encounter maximum recursion depth exceeded in comparison in Python when trying to find the factorial of 10000 using the function we just created.
Is there a way to optimise it if we still want to use recursion? Yes, there is this concept called Tail Recursion Optimisation. A function is tail-recursive if it ends by returning the value of the recursive call — whereas if any further processing is done on the return value of the recursive call the function is non tail-recursive. For example, in our case, the value of factorial(n-1) is used to multiply n. Computers are smart and if they know we are not going to do anything else with the return value, they will not add another stack and reuse the existing one. Thus, in theory we will not encounter the error of maximum recursion depth exceeded in comparison with tail recursion optimisation.
Ok, so how do we modify our function so that it is tail recursion optimised? Storing the intermediate value as a parameter might help with our problem:
This function could be exactly what we want — except that it doesnt work :(
While some programming language automatically recognise and optimise tail recursive function, Python is one that prefers to have proper tracebacks. The creator of Python language, Guido van Rossum also mentioned in two of his blogs (link & link) how he dislikes the tail recursion optimisation. He believes enabling tail recursion optimisation might be confusing for users who inadvertently write something recursive and needs debugging. It is also different fundamental beliefs by different computer scientists. I will not comment on the opinions here, but I believe we should always be encouraged to think of optimising our functions, instead of just getting them to work, so I have done some research on a couple of ways we could ‘tactically’ implement tail recursion and present here in case the readers are interested.
Firstly, we could create a decorator (for the concept of decorator in Python, please read up here :) for our function to make it tail call optimised.
Another way to avoid the errormaximum recursion depth exceeded in comparisonis to use an iterative function instead of a recursive function
