Python: Introduction to Recursion

I have been asked recently to write up a description on recursion in regards to python recursive functions. I figured this is a topic that generally confuses most engineers that I work with and is probably worthy of a quick blog post.

So first of all what is recursion?

Recursive functions are functions that call themselves in their definition. Because a recursive function calls on itself to perform its task, it can make jobs that contain identical work on multiple data objects easier to conceptualize, plan and write. Recursion can also be quite taxing on the server in which it is being ran and also has limitations which can sometimes cause issues in the future. For example recursive functions, by default, Windows has a recursion limit of 1000 (as does OSX). Linux, depending on the flavor, can range but generally is 2147483647 (2³¹ – 1).

*note to determine the value set on your system, open your python interpreter and run the following:

1
2

import sys
sys.getrecursionlimit()

Another thing to consider when writing a recursive function is that, recursion is indeed the best approach. I have seen instances where introduction can actually cause code complication along with poor performance vs. other design patterns.

1
2

def some_func(z):
    some_func(z)

Now the above example has an obvious issue in the fact that it never returns which causes a loop. This loop will continue to iterate until it reaches the system set limitation (as described previously). If you were to run the above code the end result would be the following snippet.

1
2
3
4

  File "<stdin>", line 2, in some_func
  File "<stdin>", line 2, in some_func
  File "<stdin>", line 2, in some_func
RuntimeError: maximum recursion depth exceeded

Intro to base cases

To avoid the previous example of recursion running uncontrollably until reaching the limits of the system, we have conditionals which are required to properly gate recursion. This means that functions that make use of recursion require conditions to be satisfied in order to either continue to recursively call itself or return. The common conditionals used are if/else.

Example recursion code snippet

The most common example to describe usage of recursion is within the factoring of factorial for a given number. In the spirit of this, I am going to provide a code example of using recursion to determine the factorial for a given number. As a quick explanation, if your unfamiliar with factorials. A factorial is a product of multiplication: the number resulting from multiplying a whole number by every whole number between itself and 1 inclusive. (n!, or n * n-1 * n-2 … 0).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

"""
An example of a factorial number is the following:
5! = 5 * 4 * 3 * 2 * 1
Or 
5! = 5 * 4!
Etc...
"""


def factorial(number):
    if number <= 1:
        """
           return 1, which will also unwind all of the numbers 
           included in determining the factorial.
        """
        return 1
    else:
        """
           Call this function again recursively only subtracting
           1 prime number from the previously provided number.
        """
        return number * factorial(number-1)

print factorial(5)

By copying the above code and executing in within python you will be provided with the factorial value of 5!. The expected return number is 120.

A more in depth explanation of recursion can be found http://interactivepython.org/courselib/static/pythonds/Recursion/recursionsimple.html

I plan on doing a part 2 for this post in the near future so if you found this interesting that look out for it.