Recursive Functions in Python
Recursive Functions in Python
You might not realise this, but recursions are very common. A lot of well-known acronyms are recursive, for example:
- Do you know what VISA (as in the VISA card in your wallet) stands for? It is the acronym for “Visa International Service Association”.
- Maybe you are familiar with YAML files, do you know what YAML stands for? YAML Ain’t Markup Language
- You might even be listening to music reading this article, and if you are not using Bluetooth headphones, you could be using the “JACK Audio Connection Kit” plug of your computer.
With these example in mind, even if you have never heard of recursion before, you can get an idea of what recursion is. It is just something that refers to itself.
Now, if I tell you that you can build a function that calls itself. That recursive function is going to be similar to a for loop and, in all cases, it can be substituted by a for loop (sometimes it can be very painful to try to solve a problem using an iteration process instead of recursion one). The contrary is also true: every for loop can be converted to a recursive function.
Example
A great way to illustrate recursive functions is to calculate the factorial of a number.
The factorial of an integer
nis the product of all positive integers less than or equal ton:
In the following code snippets, you will find the built-in method, an example of a for loop, a while loop example, and a recursive function example:
You will notice both the while loop and the recursive function have a base/terminal case. the while loop stops when i = number, whilst if number == 0 stops the recursion process. The recursive function would carry on multiplying negative numbers if this base case wasn’t implemented (and the while loop, positive ones).
Limitations
Unlike the while loop, which will stop when your computer has crashed, the recursive function will stop after 1000 calls. If you want to know what the factorial of 1001 is (or if there is no base case implemented), you are going to face the following error:
RuntimeError: maximum recursion depth exceeded
You can increase the recursion limit if you need to call the function more often than a thousand times by adjusting the recursion limit:
import sys
sys.setrecursionlimit(1_500)Because of this limitation, recursive functions are not the best way to calculate the factorial of high numbers. However, they are a pretty nifty way to crawl through JSON files or to create a directory tree:
# Output/home/antoine/.jupyter/
L--migrated
L--jupyter_notebook_config.py
L--/home/antoine/.jupyter/nbconfig
L--L--edit.json
L--L--notebook.json
Final Thoughts
Recursion is not something you will implement everyday, but it is used in several built-in modules like os (which handles renaming and deleting directories, for example). All in all, and although the recursion process can be mind bending, recursion is the easiest way to solve some problems like the towers of Hanoi.
