How to do recursion in Python

In Python, recursion allows a function to call itself to solve a problem. This technique simplifies complex tasks when you break them into smaller, more manageable subproblems.

You will explore key recursive techniques and practical tips for implementation. You'll also discover real-world applications and get essential advice to debug your recursive functions effectively.

Basic factorial calculation with recursion

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

print(factorial(5))--OUTPUT--120

The factorial function breaks down the problem using two key recursive principles:

• Base Case: The condition if n == 0 or n == 1 acts as the function's exit strategy. It provides a concrete answer for the smallest possible subproblem, which prevents the function from calling itself infinitely.
• Recursive Step: The line return n * factorial(n - 1) is where the function calls itself with a smaller argument. This process repeats until it hits the base case, at which point the chain of multiplications resolves back up to the original call.

Essential recursion patterns

Building on the factorial example, you'll tackle more complex patterns like the fibonacci sequence, learn to implement safer base cases, and work with multiple parameters.

Using the fibonacci sequence recursively

def fibonacci(n):
if n <= 1:
return n
return fibonacci(n-1) + fibonacci(n-2)

for i in range(7):
print(fibonacci(i), end=" ")--OUTPUT--0 1 1 2 3 5 8

The fibonacci function calculates each number by summing the two that come before it. Unlike the single call in the factorial example, this function makes two recursive calls in its return statement, creating a branching effect.

• Base Case: The condition if n <= 1 handles the sequence's first two values, 0 and 1, which provides the necessary stopping point for the recursion.
• Recursive Step: The expression fibonacci(n-1) + fibonacci(n-2) splits the problem into two smaller, identical subproblems until it reaches the base cases.

Implementing base cases for recursion safety

def power(base, exponent):
if exponent < 0:
raise ValueError("Exponent must be non-negative")
if exponent == 0:
return 1
return base * power(base, exponent - 1)

print(power(2, 4))--OUTPUT--16

The power function shows how to build safer recursive functions by handling multiple conditions. It includes two distinct base cases to manage different scenarios effectively.

• The first check, if exponent < 0, acts as a guard. It validates the input and raises a ValueError for negative exponents, preventing unexpected behavior.
• The second base case, if exponent == 0, serves as the successful exit point, returning 1 to stop the recursion.

This layered approach makes your function more robust and predictable.

Using recursion with multiple parameters

def gcd(a, b):
if b == 0:
return a
return gcd(b, a % b)

print(f"GCD of 48 and 18 is: {gcd(48, 18)}")--OUTPUT--GCD of 48 and 18 is: 6

The gcd function shows how recursion can handle multiple parameters that change with each call. It calculates the greatest common divisor of two numbers, a and b, by cleverly reducing the problem with each step.

• Base Case: The recursion stops when b equals 0. At this point, the value of a is the greatest common divisor.
• Recursive Step: The function calls itself, but it swaps the parameters. It uses b as the new first argument and the remainder of a % b as the new second argument, progressively simplifying the calculation.

Advanced recursion techniques

Building on those foundational patterns, you'll now tackle performance optimization with memoization and tail recursion, and handle intricate data by traversing nested structures.

Optimizing recursion with memoization

def fib_memo(n, memo={}):
if n in memo:
return memo[n]
if n <= 1:
return n
memo[n] = fib_memo(n-1, memo) + fib_memo(n-2, memo)
return memo[n]

print(fib_memo(30)) # Much faster than naive implementation--OUTPUT--832040

The naive fibonacci function is inefficient because it recalculates the same values repeatedly. Memoization solves this by storing—or “memoizing”—the results of expensive function calls. In fib_memo, a dictionary named memo acts as a cache to store previously computed values.

• The function first checks if the result for n already exists in memo. If it does, it returns the stored value immediately.
• If not, it calculates the result, saves it to memo, and then returns it. This ensures each Fibonacci number is computed only once.

Implementing tail recursion for efficiency

def factorial_tail(n, accumulator=1):
if n == 0:
return accumulator
return factorial_tail(n - 1, n * accumulator)

print(factorial_tail(5))--OUTPUT--120

Tail recursion is a pattern where the recursive call is the function's final action. The factorial_tail function uses an accumulator to pass the intermediate result down with each call, so no calculations are needed after the recursive call returns.

• When n reaches 0, the base case returns the final value stored in the accumulator.
• The recursive step passes the current result—n * accumulator—forward to the next call.

It's worth noting that Python doesn't perform tail call optimization, so this is more of a structural pattern here than a direct performance boost.

Traversing nested data structures recursively

def sum_nested_lists(lst):
total = 0
for item in lst:
if isinstance(item, list):
total += sum_nested_lists(item)
else:
total += item
return total

print(sum_nested_lists([1, 2, [3, 4, [5, 6]], 7]))--OUTPUT--28

Recursion is ideal for navigating unpredictable data structures, like lists nested within other lists. The sum_nested_lists function iterates through each element, using isinstance() to check its type. This allows it to handle both numbers and sub-lists differently.

• If an item is a list, the function calls itself to process the nested list, adding the result to the running total.
• If an item isn't a list, it's treated as the base case. The number is simply added to the total, and that branch of recursion ends.

Move faster with Replit

Replit is an AI-powered development platform that transforms natural language into working applications. You can describe what you want to build, and Replit Agent creates it—complete with databases, APIs, and deployment.

The recursive techniques from this article can be turned into production-ready tools. For example, Replit Agent can help you:

• Build a utility that calculates the total value of nested financial transactions in a JSON file, using logic similar to the sum_nested_lists function.
• Create a financial modeling tool that uses memoized recursion, like in fib_memo, to quickly calculate complex growth projections.
• Deploy a fraction simplification calculator that leverages the Euclidean algorithm from the gcd function to reduce fractions instantly.

Try turning your own ideas into applications. Describe what you want to build, and let Replit Agent handle the coding, testing, and deployment for you.

Common errors and challenges

Navigating recursion in Python means knowing how to sidestep common errors like infinite loops and incorrect memoization.

Avoiding RecursionError with proper base cases

One of the most frequent issues you'll encounter is a RecursionError: maximum recursion depth exceeded. This happens when a recursive function calls itself too many times without hitting its base case. Python sets this limit to prevent a stack overflow, where the system runs out of memory to track the function calls.

• The Cause: This error almost always points to a flawed or missing base case. If the condition to stop the recursion is never met, the function will call itself indefinitely until Python intervenes.
• The Fix: Always ensure your function has a well-defined base case that is guaranteed to be reached. Double-check that each recursive call brings the arguments progressively closer to that stopping condition.

Fixing mutable default argument bugs in memoization

When implementing memoization, a subtle bug can arise from using mutable default arguments, like a dictionary or list. In the fib_memo(n, memo={}) example, the memo dictionary is created only once when the function is defined, not each time it's called. This means the cache persists across separate calls, which can lead to incorrect results if you run the function with different inputs in the same program.

• The Cause: The default memo={} object is shared. If you call fib_memo(10) and then fib_memo(5), the cache from the first call contaminates the second.
• The Fix: The standard practice is to set the default argument to None and create a new dictionary inside the function. You'd check if memo is None: and then initialize memo = {}. This ensures every top-level call to your function starts with a fresh, empty cache.

Preventing infinite recursion with proper problem reduction

Infinite recursion occurs when the recursive step fails to reduce the problem, preventing it from ever reaching the base case. Unlike a RecursionError caused by a deep but finite process, this is a logical flaw where the function makes no progress. The arguments in subsequent calls remain the same or move away from the base case.

• The Cause: This often stems from a typo or logical error in the recursive call. For example, in the gcd function, calling gcd(a, b) instead of gcd(b, a % b) would cause an infinite loop if b is not zero.
• The Fix: Scrutinize the arguments passed to the recursive call. Confirm that each call simplifies the problem in a meaningful way, ensuring it will eventually converge on the base case.

Avoiding RecursionError with proper base cases

A missing base case is the usual suspect behind a RecursionError. Without a clear stopping point, the function calls itself until Python's recursion limit is hit. The following countdown function demonstrates this problem in action, creating an unstoppable loop.

def countdown(n):
print(n)
return countdown(n - 1)

countdown(10)

This function calls countdown(n - 1) unconditionally, so it continues printing numbers past zero into the negatives. With no exit condition, it runs until Python's recursion limit is hit. The corrected version below demonstrates the fix.

def countdown(n):
print(n)
if n <= 0:
return
return countdown(n - 1)

countdown(10)

The corrected countdown function introduces a base case with if n <= 0: return. This condition stops the recursion once n reaches zero, preventing the infinite loop and the resulting RecursionError.

Without this check, the function would keep calling itself with negative numbers. You should always ensure your recursive functions have a clear exit strategy that is guaranteed to be met, as this is the most common pitfall in recursive programming.

Fixing mutable default argument bugs in memoization

A common memoization pitfall is using a mutable default argument like memo={}. Because the dictionary is created only once, it doesn't reset between function calls, leading to contaminated results. The following fib_memo function shows this bug in action.

def fib_memo(n, memo={}):
if n in memo:
return memo[n]
if n <= 1:
return n
memo[n] = fib_memo(n-1, memo) + fib_memo(n-2, memo)
return memo[n]

print(fib_memo(5))
print(fib_memo(3)) # Returns unexpected result

The call to fib_memo(3) reuses the cache populated by fib_memo(5), causing it to return a stored value instead of recalculating. The corrected code below demonstrates the standard fix for this behavior.

def fib_memo(n, memo=None):
if memo is None:
memo = {}
if n in memo:
return memo[n]
if n <= 1:
return n
memo[n] = fib_memo(n-1, memo) + fib_memo(n-2, memo)
return memo[n]

print(fib_memo(5))
print(fib_memo(3)) # Returns correct result

The corrected fib_memo function fixes the bug by setting the default argument to memo=None. Inside the function, a new dictionary is created only if memo is None. This simple change ensures that every top-level call gets a fresh, empty cache, so calculations from one call won't contaminate the next. You should always be cautious when using mutable objects like lists or dictionaries as default arguments in Python functions.

Preventing infinite recursion with proper problem reduction

Infinite recursion occurs when the recursive step fails to simplify the problem, so it never reaches the base case. This isn't about depth; it's a logical flaw where the function makes no progress toward a solution, getting stuck in a loop.

The following find_zero function demonstrates this error. It's designed to locate the number 0 in a list, but a bug in its recursive call—find_zero(lst, index)—prevents it from ever moving forward through the list.

def find_zero(lst, index=0):
if lst[index] == 0:
return index
return find_zero(lst, index) # Bug: index isn't incremented

find_zero([1, 2, 0, 3])

The function calls itself with an unchanged index, so it repeatedly checks the same list element. This creates an infinite loop because the search never progresses. The corrected code below demonstrates the simple fix.

def find_zero(lst, index=0):
if index >= len(lst):
return -1
if lst[index] == 0:
return index
return find_zero(lst, index + 1) # Fixed: index is incremented

print(find_zero([1, 2, 0, 3])) # Returns 2

The corrected find_zero function fixes the infinite loop by incrementing the index in each recursive call with find_zero(lst, index + 1). This ensures the function progresses through the list instead of getting stuck. A new base case, if index >= len(lst):, was also added to handle cases where the target isn't found, preventing an error. Always confirm your recursive calls make tangible progress toward a solution to avoid this logical flaw.

Real-world applications

With a solid grasp of recursive patterns and pitfalls, you can apply these techniques to real-world challenges like navigating file systems or solving complex puzzles.

Finding files with os module recursion

Recursion is perfectly suited for navigating a file system, allowing you to write a function with the os module that searches through a directory and all its subdirectories.

import os

def find_python_files(directory):
result = []
for item in os.listdir(directory):
path = os.path.join(directory, item)
if os.path.isfile(path) and path.endswith(".py"):
result.append(path)
elif os.path.isdir(path):
result.extend(find_python_files(path))
return result

print(find_python_files(".")[:2])

The find_python_files function navigates a file tree to locate all Python scripts. It iterates through each item in a starting directory.

• When it finds a file ending in .py, it adds the file's path to a list. This acts as a base case, ending that particular search path.
• When it encounters a directory, it calls itself in a recursive step to search inside that new directory. The results from this nested search are then added to the main list with extend().

Solving Tower of Hanoi puzzle with tower_of_hanoi()

The Tower of Hanoi is a classic puzzle that perfectly illustrates how a complex problem can be broken down into simpler, recursive steps.

def tower_of_hanoi(n, source, auxiliary, target):
if n == 1:
print(f"Move disk 1 from {source} to {target}")
return
tower_of_hanoi(n-1, source, target, auxiliary)
print(f"Move disk {n} from {source} to {target}")
tower_of_hanoi(n-1, auxiliary, source, target)

tower_of_hanoi(3, 'A', 'B', 'C')

The tower_of_hanoi function breaks the problem of moving n disks into three core steps, cleverly redefining the source, auxiliary, and target pegs in each recursive call.

• First, it moves n-1 disks from the source to the auxiliary peg.
• Next, it moves the largest disk (n) from the source to the target.
• Finally, it moves the n-1 disks from the auxiliary peg to the target.

The recursion stops when it hits the base case, if n == 1:, which handles the simple action of moving a single disk.

Get started with Replit

Put these recursive patterns into practice with Replit Agent. Try prompts like, “Build a web app that simplifies fractions using gcd logic,” or “Create a tool that recursively scans a directory to calculate total file size.”

The agent writes the code, tests for errors, and deploys the app from your description. Start building with Replit and bring your ideas to life.