Python Recursion: a Trampoline from the Mutual Head to the Memoized Nested Tail | Ezequiel Leonardo Castaño Personal Website

Recursion is a key concept of programming. However, it is usually only superficially explored. There are different ways of having recursion, this post will illustrate them using Python examples, call graphs and step-by-step runs. Including cases of head, tail, nested and mutual recursion. For each case, the call graph will be shown.

Many if not all programming courses introduce the factorial function at some point. This function has great mathematical importance and yet it is simple enough to showcase how recursion works. However, the approach towards it and recursion, in general, is usually superficial.

This post abuses the fact that, in Python, when a function is defined multiple times only the last definition is used for future references. There will be many refinements over the definitions and to avoid any confusion, names will not be changed to reflect that, they all do the same. To further reinforce this idea, an assert statement will be added to show that results do not change even if the definition changes.

Between the for loop and the while loop implementation differences are visible. The for-loop approach is usually the one found in many sources online, it is short, uses only basic constructs and does the job. Whereas the while approach uses one extra variable, that being said, both are valid and share the same time and space complexity.

Leave a Comment