Recursive function for calculating <code>n! </code>implemented in Python:Behind the scenes, each recursive call adds a stack frame (containing its execution context) to the call stack until we reach the base case. Then, the stack begins to unwind as each call returns its results:A demonstration should make things clearer. Let’s calculate <code>1 + 2 + 3 ⋅⋅⋅⋅ + 10 </code>using recursion. The state that we have to maintain is (current number we are adding, accumulated sum till now) .

Power of python recursion

Learn how to work with recursion in your Python programs by mastering concepts such as recursive functions and recursive data structures.

computerscience

Computer Science

Now that we have some intuition about recursion, let’s introduce the formal definition of a recursive function. A recursive function is a function defined in terms of itself via self-referential expressions.

This means that the function will continue to call itself and repeat its behavior until some condition is met to <a dir="ltr" href="https://realpython.com/python-return-statement/">return </a>a result. All recursive functions share a common structure made up of two parts: base case and recursive case.

To demonstrate this structure, let’s write a recursive function for calculating <code dir="ltr">n! </code>:

<ol><li>Decompose the original problem into simpler instances of the same problem. This is the recursive case: <pre><code>n! = n x (n−1) x (n−2) x (n−3) ⋅⋅⋅⋅ x 3 x 2 x 1 n! = n x (n−1)! </code> </pre> </li><li>As the large problem is broken down into successively less complex ones, those subproblems must eventually become so simple that they can be solved without further subdivision. This is the base case: <pre><code>n! = n x (n−1)! n! = n x (n−1) x (n−2)! n! = n x (n−1) x (n−2) x (n−3)! ⋅ ⋅ n! = n x (n−1) x (n−2) x (n−3) ⋅⋅⋅⋅ x 3! n! = n x (n−1) x (n−2) x (n−3) ⋅⋅⋅⋅ x 3 x 2! n! = n x (n−1) x (n−2) x (n−3) ⋅⋅⋅⋅ x 3 x 2 x 1! </code> </pre> </li> </ol>

Here, <code dir="ltr">1! </code>is our base case, and it equals <code dir="ltr">1 </code>.

Recursive function for calculating <code dir="ltr">n! </code>implemented in Python:

Behind the scenes, each recursive call adds a stack frame (containing its execution context) to the call stack until we reach the base case. Then, the stack begins to unwind as each call returns its results:

When dealing with recursive functions, keep in mind that each recursive call has its own execution context, so to maintain state during recursion you have to either:

<ul><li>Thread the state through each recursive call so that the current state is part of the current call’s execution context </li><li>Keep the state in global scope </li> </ul>

A demonstration should make things clearer. Let’s calculate <code dir="ltr">1 + 2 + 3 ⋅⋅⋅⋅ + 10 </code>using recursion. The state that we have to maintain is (current number we are adding, accumulated sum till now) .

Here’s how you do that by <a dir="ltr" href="https://realpython.com/intro-to-python-threading/">threading </a>it through each recursive call (i.e. passing the updated current state to each recursive call as arguments):

Here’s how you maintain the state by keeping it in global <a dir="ltr" href="https://realpython.com/python-namespaces-scope/">scope </a>:

I prefer threading the state through each recursive call because I find global mutable state to be evil, but that’s a discussion for a later time.

A data structure is recursive if it can be deﬁned in terms of a smaller version of itself. A <a dir="ltr" href="https://realpython.com/python-lists-tuples/">list </a>is an example of a recursive data structure. Let me demonstrate. Assume that you have only an empty list at your disposal, and the only operation you can perform on it is this:

Using the empty list and the <code dir="ltr">attach_head </code>operation, you can generate any list. For example, let’s generate <code dir="ltr">[1, 46, -31, "hello"] </code>:

<ol><li>Starting with an empty list, you can generate any list by recursively applying the <code dir="ltr">attach_head </code>function, and thus the list data structure can be defined recursively as: <pre><code>+---- attach_head(element, smaller list) list = + +---- empty list </code> </pre> </li><li>Recursion can also be seen as self-referential function composition. We apply a function to an argument, then pass that result on as an argument to a second application of the same function, and so on. Repeatedly composing <code dir="ltr">attach_head </code>with itself is the same as <code dir="ltr">attach_head </code>calling itself repeatedly. </li> </ol>

List is not the only recursive data structure. Other examples include <a dir="ltr" href="https://realpython.com/python-sets/">set </a>, tree, <a dir="ltr" href="https://realpython.com/python-dicts/">dictionary </a>, etc.

Recursive data structures and recursive functions go together like bread and butter. The recursive function’s structure can often be modeled after the definition of the recursive data structure it takes as an input. Let me demonstrate this by calculating the sum of all the elements of a list recursively:

The Fibonacci numbers were originally deﬁned by the Italian mathematician Fibonacci in the thirteenth century to model the growth of rabbit populations. Fibonacci surmised that the number of pairs of rabbits born in a given year is equal to the number of pairs of rabbits born in each of the two previous years, starting from one pair of rabbits in the ﬁrst year.

To count the number of rabbits born in the nth year, he deﬁned the recurrence relation:

Let’s write a recursive function to compute the nth Fibonacci number:

Naively following the recursive deﬁnition of the nth Fibonacci number was rather inefficient. As you can see from the output above, we are unnecessarily recomputing values. Let’s try to improve <code dir="ltr">fibonacci_recursive </code>by caching the results of each Fibonacci computation Fk :

<a dir="ltr" href="https://realpython.com/lru-cache-python/"><code dir="ltr">lru_cache </code> </a>is a <a dir="ltr" href="https://realpython.com/primer-on-python-decorators/">decorator </a>that caches the results. Thus, we avoid recomputation by explicitly checking for the value before trying to compute it. One thing to keep in mind about <code dir="ltr">lru_cache </code>is that since it uses a dictionary to cache results, the positional and keyword arguments (which serve as keys in that dictionary) to the function must be hashable.

Python doesn’t have support for <a dir="ltr" href="https://en.wikipedia.org/wiki/Tail_call">tail-call elimination </a>. As a result, you can cause a stack overflow if you end up using more stack frames than the <a dir="ltr" href="https://docs.python.org/3.6/library/sys.html#sys.getrecursionlimit">default call stack depth </a>:

Keep this limitation in mind if you have a program that requires deep recursion.

Also, Python’s mutable data structures don’t support structural sharing, so treating them like <a dir="ltr" href="https://en.wikipedia.org/wiki/Persistent_data_structure">immutable data structures </a>is going to negatively affect your space and <a dir="ltr" href="https://realpython.com/python-memory-management/#garbage-collection">GC (garbage collection) </a>efficiency because you are going to end up unnecessarily copying a lot of mutable objects. For example, I have used this pattern to decompose lists and recurse over them:

I did that to simplify things for the sake of clarity. Keep in mind that tail is being created by copying. Recursively doing that over large lists can negatively affect your space and GC efficiency.

I was once asked to explain recursion in an interview. I took a sheet of paper and wrote <code dir="ltr">Please turn over </code>on both sides. The interviewer didn’t get the joke, but now that you have read this article, hopefully you do 🙂 Happy Pythoning!

Thinking Recursively in Python – Real Python

Power of python recursion

samuel bancroft's ideas are part of this journey:

Related collections

Similar ideas