Recursion in Python

Recursion is a concept in Python where a function calls itself as a method of solving smaller parts of a problem. This process continues until it breaks down big tasks into more manageable steps until the simplest step can be handled directly.

When trying to understand recursion as it relates to Python, the idea sounds complex, but it is quite natural once you get a hang of it. In this guide, we’ll explore what recursion is, how it is used in Python, and how to compute the Fibonacci sequence using recursion.

What is Recursion?

In Python, recursion is a way of solving problems you can break down into similar sub-problems. Imagine you are trying to find a specific book from a stack of books on your shelf. You can go through the stack quickly by taking the top book from the stack, and checking if it’s the one you’re looking for. If it isn’t, you go on to repeat the process with the next book. You keep doing this till you find the book or till there are no books left.

Your repetitive approach of handling one book at a time, and moving to the next is just like recursion. You break down a problem (searching for a book) into smaller, similar sub-problems (checking each book one by one) until you get to the base case (either finding the book or running out of books)

Explaining Recursion with Simple Code

Before we get into recursion in Python, let’s explore a simple code example. Imagine, you want to write a code that counts down from 9 to 0, you can write this using recursion where the function keeps calling itself until it reaches a stopping point.

def countdown(x):
    if x > 9:
        x = 9
    if x < 0:
        return
    print(x)
    countdown(x - 1)

countdown(10)

• Function: countdown (x) takes an integer x as input.
• Assigning x: If x is greater than9, it sets x to 9 so that it counts down from 9 to 0.
• Base case: If x is less than0, the function stops (does not print anything).
• Print Statement: It prints the current value of x.
• Recursive Call: It calls itself with x - 1, effectively counting down.

Here’s the output of the code:

9
8
7
6
5
4
3
2
1
0

In Python, recursion involves using functions which are blocks of reusable code that perform specific tasks. A recursive function is a function that calls itself and aims at solving the same problem but on a smaller scale each time. However, for a recursion to run properly, it must have a Base Case which is the stopping condition. This condition defines when the function in question should stop calling itself, otherwise, it would run forever.

Use of Recursion in Python

One of the best ways to see recursion in action is through factorial calculation. If you’re unfamiliar with factorials, don’t worry — it’s a simple concept.

A factorial is the product of all positive numbers from 1 to n. Think of it as a countdown where you keep multiplying until you get to 1. Factorial is written as n! (read a “n factorial”)

Get Dubem Obinna-Esiowu’s stories in your inbox

Join Medium for free to get updates from this writer.

Remember me for faster sign in

Here’s an example: 5!

5 × 4 × 3 × 2 × 1 = 120

3!

3 × 2 × 1 = 6

Now, let’s think of a way to calculate a factorial in a structured way: To get 5! , you can multiply 5 × 4! To get 4! , you multiply 4 × 3! This pattern continues until you reach 1! , which is just 1. Instead of using loops, we can write a recursive function in Python to handle this repetition:

def factorial(n):
    if n == 1:  # Base case: Stop when n is 1
        return 1
    return n * factorial(n - 1)  # Recursive case: Multiply n by (n-1)!

How Python Executes Recursive Functions

When you call factorial (5), Python does this:

factorial (5) → calls factorial (4)
factorial (4) → calls factorial (3)
factorial (3) → calls factorial (2)
factorial (2) → calls factorial (1)
factorial (1) → Base case reached, returns 1

Then, Python resolves each function call in reverse:

factorial (2): 2 × 1 = 2
factorial (3): 3 × 2 = 6
factorial (4): 4 × 6 = 24
factorial (5): 5 × 24 = 120

Python breaks down a problem into smaller steps and solves it step by step just like recursion in theory.

Structure of a Recursive Function

A recursive function has two parts:

• Base Case: This is the simplest possible case where the function returns a known value without making any more recursive calls.
• Recursive Case: This is where the function calls itself with a modified version of the problem, making progress towards the base case.

Factorial Calculation

Let’s try calculating the factorial of a number. The factorial of a non-negative integer n, denoted as n!, is the product of all positive integers less than or equal to n!.

def factorial(n):
    # Base case
    if n == 0:
        return 1
    # Recursive case
    else:
        return n * factorial(n - 1)

# Example usage
 print(factorial(5))  # Output: 120 (5! = 5 * 4 * 3 * 2 * 1)

In this function:

• The base case (if n == 0) ensures the recursion terminates.
• The recursive case (return n * factorial(n — 1)) breaks down the problem into smaller subproblems until it reaches the base case.

Computing the Fibonacci Sequence Using Recursion

Another classic example is generating the Fibonacci sequence, where each number is the sum of the two preceding ones, starting from 0 and 1.

def fibonacci(n):
    # Base cases
    if n == 0:
        return 0
    elif n == 1:
        return 1
    # Recursive case
    else:
        return fibonacci(n - 1) + fibonacci(n - 2)

# Example usage
print(fibonacci(7))  # Output: 13 (Fibonacci sequence: 0, 1, 1, 2, 3, 5, 8, 13)

Here:

• Base cases (n == 0 and n == 1) halt the recursion.
• Recursive calls (return fibonacci(n — 1) + fibonacci(n — 2)) build up the sequence.

Using Recursion to Traverse Tree Data Structures

Recursion is particularly handy for traversing hierarchical data structures like trees. Consider a simplified example:

class TreeNode:
    def __init__(self, value):
        self.value = value
        self.children = []

# Example of traversing a tree recursively
def traverse_tree(node):
    print(node.value)
    for child in node.children:
        traverse_tree(child)

# Usage example
root = TreeNode('A')
root.children = [TreeNode('B'), TreeNode('C')]
root.children[0].children = [TreeNode('D'), TreeNode('E')]

traverse_tree(root)

This recursively prints out the values of nodes in a tree structure.

Conclusion

Recursion is one of those concepts in programming that can feel a bit tricky at first, but once you get the hang of it, it opens up a whole new way of thinking about problems. It’s especially useful when dealing with tasks that naturally break down into smaller versions of themselves — like calculating factorials, generating Fibonacci numbers, or traversing trees.

The key to using recursion effectively is to make sure each recursive call brings you closer to a base case. Without that, your code could keep calling itself indefinitely, leading to a stack overflow error. Performance is another thing to keep in mind — recursion can be elegant, but if you’re not careful, it can also be inefficient.

The best way to get comfortable with recursion is to practice. Start with simple examples, visualize how the function calls stack up and unwind, and soon, you’ll start recognizing where recursion is the perfect tool for the job.