Recursion¶

You’ve seen functions that call other functions.

If a function calls itself, we call that recursion

Like with other functions, a call within a call establishes a call stack

With recursion, if you are not careful, this stack can get very deep.

Python has a maximum limit to how much it can recurse. This is intended to save your machine from running out of RAM.

Recursion is especially useful for a particular set of problems.

For example, take the case of the factorial function.

In mathematics, the factorial of an integer is the result of multiplying that integer by every integer smaller than it down to 1.

5! == 5 * 4 * 3 * 2 * 1

We can use a recursive function nicely to model this mathematical function:

1! = 1
2! = 2 * 1  =  2 * 1!
3! = 3 * 2 * 1 = 3 * 2!

So we have a pattern here – each value can be defined in terms of the previous value.

So generically:

1! = 1
n! = n * (n-1)!

How would we put that in code? Pretty straightforward translation:

def factorial(n):
    return n * factorial(n-1)

That was pretty easy – what happens when we run it?

In [2]: factorial(3)
---------------------------------------------------------------------------
RecursionError                            Traceback (most recent call last)
<ipython-input-2-3fd9b1939623> in <module>()
----> 1 factorial(3)

<ipython-input-1-5ff805d50ea6> in factorial(n)
      1 def factorial(n):
----> 2     return n * factorial(n-1)

... last 1 frames repeated, from the frame below ...

<ipython-input-1-5ff805d50ea6> in factorial(n)
      1 def factorial(n):
----> 2     return n * factorial(n-1)

RecursionError: maximum recursion depth exceeded

OOPS! that didn’t work – why not? Let’s add a print…

def factorial(n):
    print("factorial called with", n)
    return n * factorial(n-1)

And call it:

In [5]: factorial(3)
factorial called with 3
factorial called with 2
factorial called with 1
factorial called with 0
factorial called with -1
factorial called with -2
factorial called with -3
factorial called with -4
factorial called with -5
...
<ipython-input-3-54c2cb2bf478> in factorial(n)
      1 def factorial(n):
      2     print("factorial called with", n)
----> 3     return n * factorial(n-1)

RecursionError: maximum recursion depth exceeded while calling a Python object

Now it’s clear what’s going on – each time you call the function, it calls itself with a value one less – but then it just keeps going into the deep negative numbers, and only stops because Python reaches its recursion limit.

This makes clear a core requirement of recursive functions:

Recursive functions must have a termination criteria!

That is, there must be a case (or more than one) for which they return a direct value. What should that be for factorial? Well, it’s part of the definition that 1! == 1 – so let’s put that in our function:

def factorial(n):
    print("factorial called with", n)
    if n == 1:
        return 1
    return n * factorial(n-1)

and try that:

In [7]: factorial(3)
factorial called with 3
factorial called with 2
factorial called with 1
Out[7]: 6

Much better! Try it out now with various values, and maybe without the print:

In [14]: factorial(1)
Out[14]: 1

In [15]: factorial(2)
Out[15]: 2

In [16]: factorial(3)
Out[16]: 6

In [17]: factorial(4)
Out[17]: 24

Looking good!

Exercise for the reader: What happens if you pass in a negative number? Think about it first, before you try it. Hint – it won’t work! How would you change your code to make it more robust?

Summary¶

Whenever you have a function that can be defined in terms of itself, you have a use case for recursion. It can make for nice compact, clear code.
Python will create a new “stack frame” for each call to the function – so each call is kept separate, with separate local variables.

But:

Python has a limited recursion depth – so it can’t be used for “big” problems.
You do need to make sure the calls will terminate.