# Recursion in Python Programming — Compucademy

In this article we discuss recursion in Python programming. Recursion is a fundamental concept in Computer Science, and regardless of what your development goals are, it is good to have an understanding of at least the basics.

Topics covered:

• The basic concept of recursion
• What is a base case?
• Some examples of recursive algorithms
• Visualizing recursion

In terms of day-to-day development, the amount you use recursion will vary by context. Some developers may make little or no explicit use of it while for others it will be a mainstay. Regardless, recursion is part of the very fabric of computing, and even if you don’t use it explicitly in your everyday work, you can bet it’s happening a whole lot behind the scenes.

Here are some examples of where recursion is used in computing:

• traversing DOM elements
• processing recursively defined data such as that stored in trees
• command shells
• compilers and linkers
• evaluation of arithmetic expressions
• database systems

Recursion is so important and useful that almost all modern programming languages support it.

# An Example of a Recursive Algorithm in Python

To understand what recursion is, it’s probably best to look at an example first and then break it down to explain what is happening. Type this code into a new Python file.

`def countdown(n):  if n <= 0: print("LIFTOFF!")  else: print(n) countdown(n - 1)countdown(10)`

Here’s the output:

`10987654321LIFTOFF!`

What is going on here? Even though it’s a simple program, it contains the fundamental ingredients of recursion, sometimes known as “the Three Laws of Recursion.”

# Base case

A base case is essential with recursion. Without it there is no way for the algorithm to “know” when to stop. Not having one is like having a `while True` loop - i.e. you get an infinite loop, except with recursion you will eventually hit your system's maximum recursion limit. In the example above, the base case is when `n <= 0`.

# Movement toward the base case

The algorithm must approach the base case on each successive call, otherwise it can not terminate. Again comparing this to a `while` loop, not moving towards the base case is like not moving towards the condition for the while loop to exit. Each successive call in the example above has `n - 1` as its argument so we are approaching the base case. This is good.

# A recursive call

The simple yet powerful idea here is that the function definition contains a call to itself within its body. Did you notice that the function definition for `countdown()` contains a call to the function `countdown()`?

# Stages of recursion

One key thing to understand about recursion is that there are two stages to a recursive algorithm. Before anything is returned from the initial function call, all the subsequent recursive function calls are made, until the base case is reached. At that point, the call stack (which contains a frame for each function call), begins to unwind, until a value for the initial function call is returned.

This is probably best illustrated visually. Look at this representation of a call to the `factorial(n)` function, which calculates the product of decreasing values of `n` and whose mathematical symbol is `!`. For example `5! = 5 * 4 * 3 * 2 * 1`

`def factorial(n):   if n == 1:    return 1   else:    return n * factorial(n-1)print(factorial(5))`

Here’s what happens before the final value of `120` is returned and printed:

`|-- factorial(5)|  |-- factorial(4)|  |  |-- factorial(3)|  |  |  |-- factorial(2)|  |  |  |  |-- factorial(1)|  |  |  |  |  |-- return 1|  |  |  |  |-- return 2|  |  |  |-- return 6|  |  |-- return 24|  |-- return 120120>>>`

`factorial(5)` calls `factorial(4)` which calls `factorial(3)` etc, until the base case is reached ( `n == 1`), then each of the function calls returns its value, in the reverse order to that in which they were called, until the value for the initial call `factorial(5)` is returned.

We can use the same kind of diagram for our first example of a recursive algorithm, `countdown(n)` although is is less clear what is happening since nothing (actually `None`) is returned by each successive function call, as we are using `print` to output the value for each stage of the count.

`|-- countdown(5)5|  |-- countdown(4)4|  |  |-- countdown(3)3|  |  |  |-- countdown(2)2|  |  |  |  |-- countdown(1)1|  |  |  |  |  |-- countdown(0)LIFTOFF!|  |  |  |  |  |  |-- return None|  |  |  |  |  |-- return None|  |  |  |  |-- return None|  |  |  |-- return None|  |  |-- return None|  |-- return NoneNone`

# How to Master Recursion in Python

Just released on LinkedIn Learning — my Python Recursion Video Course. Take a deep dive into the concepts, techniques, and applications of recursion using Python in this fun and accessible course: Python Recursion Video Course

Learners often find recursion confusing when they first encounter it. This is completely normal. Recursion has the paradoxical quality of being both very simple and intuitive on the one hand, and seemingly confusing and complex on the other. The way to gain confidence and competence with the topic is by looking at lots of examples of recursive algorithms and, more importantly, writing them for yourself. You may also have to spend a bit of hard thinking time wrapping your head around what is happening. Having a whiteboard handy may help as you trace a particular function call and try to anticipate what happens next. Don’t be discouraged if it takes a while for your understanding of recursion to grow. It is well worth the effort!

Happy computing!

Originally published at https://compucademy.net.

Computer Science Education for the Next Generation. Teaching, Training and Resources.

## More from Compucademy

Computer Science Education for the Next Generation. Teaching, Training and Resources.