Recursion in Python

Recursion is an efficient programming technique in which a function invokes itself to find solutions for the smaller versions of the same problem. Recursion may be used in Python to solve problems such as finding factorials, tree traversals, or solving games like the Tower of Hanoi.

What is Recursion?

Get Chirag Chandel’s stories in your inbox

Join Medium for free to get updates from this writer.

Remember me for faster sign in

Simply put, recursion is a function invoking itself until it arrives at a point where it stops known as the base case. Without a base case, the recursion would continue indefinitely and eventually bring down the program (hello, stack overflow!).

Syntax of a Recursive Function

def recursive_function():
    # base case
    if condition:
        return result
    else:
        # recursive case
        return recursive_function()

Let’s look at a classic example: Calculating factorial using recursion.

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

print(factorial(5))  # Output: 120

Here’s what happens when factorial(5) is called:

factorial(5)
→ 5 * factorial(4)
→ 5 * 4 * factorial(3)
→ 5 * 4 * 3 * factorial(2)
→ 5 * 4 * 3 * 2 * factorial(1)
→ 5 * 4 * 3 * 2 * 1 → 120

Visualizing Recursion

Here’s a diagram showing how recursion works in the factorial example:

factorial(5)
   ↓
5 * factorial(4)
       ↓
   4 * factorial(3)
         ↓
     3 * factorial(2)
           ↓
       2 * factorial(1)
             ↓
           1  ← Base Case

As the function “unwinds,” it multiplies each returned value.

When to Use Recursion

Use recursion when:

• The problem can be broken down into smaller subproblems.
• You know the base case.
• Each subproblem is similar in nature to the original.

Be Careful!

Recursive functions are elegant but can be memory-intensive. Each function call adds a new layer to the call stack. Python limits the recursion depth (usually around 1000 calls) to prevent crashes.

Final Thoughts

Recursion makes code elegant and concise. Once you understand how it works, it can be a valuable tool in your coding arsenal. Just remember to define your base case clearly!

Want to dive deeper into Recursion with examples and practice problems?
Explore Recursion in Python on PrepInsta and master the concept with ease!