Learn Recursion in Python with Example

Recursion is a fundamental concept in programming that allows a function to solve problems by calling itself. It can seem tricky at first, but once you understand the flow, recursion becomes a powerful tool for solving repetitive or nested problems.

In this article, we’ll explain recursion in very simple terms and walk through an example to help you understand how recursion works.

What is Recursion?

Recursion is a method where a function solves a problem by calling itself. The function keeps splitting the problem into smaller parts and calls itself again and again until the bigger problem is solved. However, each recursive function must have two important things:

1. Base Condition: This is the condition that stops the recursion. Without it, the function will call itself indefinitely, causing a “stack overflow.”
2. Recursive Call: This is the part where the function calls itself to break the problem into smaller pieces.

Without a base condition, the function would keep calling itself forever, causing a ‘stack overflow’ error. We’ll explain the call stack soon.

For now, Let’s understand recursion with the help of an example.

Example: Printing Numbers in Reverse Order

Let’s look at an example where we print numbers in reverse order using recursion. We want to print numbers starting from n down to 1.

Source Code:

def print_reverse(n):
    # Base condition: stop when n reaches 0
    if n == 0:
        return
    print(n)        # Print the current number
    print_reverse(n - 1)   # Recursively call the function with (n - 1)

# Example: Printing numbers from 5 to 1
print_reverse(5)

If you call print_reverse(5), the output will be:

5
4
3
2
1

How Recursion Works

Let’s break this down:

1. First Call: The function print_reverse(5) is called. Since n is not 0, it prints 5 and calls itself again with n - 1, which means print_reverse(4).
2. Next Calls: This process continues, reducing n by 1 each time and calling the function again:
   • print_reverse(4) prints 4 and calls print_reverse(3).
   • print_reverse(3) prints 3 and calls print_reverse(2).
   • This keeps happening until n == 0.
3. Base Condition: When n becomes 0, the function hits the base condition and returns. This means it stops calling itself further and starts completing the previous calls.

How the Stack Works in Recursion

Recursion relies on something called the call stack. Each time a function is called, it is added to the call stack. The call stack uses a Last In, First Out (LIFO) system, meaning the last function called will be the first one to finish.

Here’s what happens in this example:

• When print_reverse(5) is called, it’s added to the stack.
• Then, print_reverse(4) is added on top of it, and so on until print_reverse(1).

When n becomes 0, the function starts popping off the stack in reverse order:

• It finishes print_reverse(1), then print_reverse(2), and so on, until the stack is empty.

Importance of the return Statement

The return statement plays a critical role in recursion. In our code, when n == 0, the function returns and stops calling itself:

if n == 0:
    return

Without this return, the function would continue calling itself indefinitely, leading to a stack overflow. The return not only stops recursion but also signals the function to start popping calls off the stack and resolving them.

In summary, the return ensures:

• The recursion ends when the base condition is met.
• Previous function calls can be completed and removed from the stack.

Conclusion

This is all about recursion in Python. I hope this article helps you understand recursion. Thank you for reading! If you’re interested in learning more about Python, click here, and I’ll see you in the next article.