Python Recursion: Syntax, Usage, and Examples

Python recursion is a technique where a function calls itself to solve a problem in a step-by-step manner. It is commonly used for solving problems that can be broken down into smaller subproblems, such as calculating factorials, Fibonacci sequences, and performing binary search.

How to Use Recursion in Python

A recursive function in Python follows a simple structure:

def recursive_function(parameters):
    if base_condition:
        return result
    else:
        return recursive_function(modified_parameters)

• Base condition: The stopping point that prevents infinite recursion.
• Recursive call: The function calls itself with modified parameters.

Example: Simple Recursion

def countdown(n):
    if n <= 0:  # Base case
        print("Done!")
    else:
        print(n)
        countdown(n - 1)  # Recursive call

countdown(5)

Output:

5
4
3
2
1
Done!

This example demonstrates recursion with a base case to stop the function.

When to Use Recursion in Python

Recursion is useful when:

1. Solving problems that can be divided into smaller subproblems
   • Examples: Factorial calculations, Fibonacci sequences, and tree traversals.
2. Working with nested data structures
   • Example: Traversing a directory structure or processing a JSON object.
3. Implementing algorithms like binary search and depth-first search
   • Recursion naturally follows the structure of these problems.

Examples of Recursion in Python

Factorial Recursion

Factorial of n (n!) is n * (n-1) * (n-2) ... * 1.

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

print(factorial(5))  # Output: 120

Fibonacci Recursion

The Fibonacci sequence follows the rule: F(n) = F(n-1) + F(n-2), where F(0) = 0 and F(1) = 1.

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

print(fibonacci(6))  # Output: 8

Binary Search with Recursion

Binary search efficiently finds an element in a sorted list by dividing the search range in half.

def binary_search(arr, target, left, right):
    if left > right:
        return -1  # Base case: target not found

    mid = (left + right) // 2
    if arr[mid] == target:
        return mid  # Base case: target found
    elif arr[mid] < target:
        return binary_search(arr, target, mid + 1, right)  # Search right half
    else:
        return binary_search(arr, target, left, mid - 1)  # Search left half

numbers = [1, 3, 5, 7, 9, 11]
print(binary_search(numbers, 7, 0, len(numbers) - 1))  # Output: 3

Learn More About Recursion in Python

Recursion Depth Limit in Python

Python limits recursion depth to prevent infinite recursion, causing a RecursionError.

import sys
print(sys.getrecursionlimit())  # Output: Typically 1000

You can modify this limit using sys.setrecursionlimit(), but increasing it too much may cause crashes.

Maximum Recursion Depth Exceeded Error

If a function calls itself too many times without reaching a base case, Python raises:

RecursionError: maximum recursion depth exceeded while calling a Python object

Tail Recursion in Python

Tail recursion is an optimization where the recursive call is the last operation in a function. Python does not optimize tail recursion, so deep recursion can still cause stack overflow.

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

print(tail_recursive_factorial(5))  # Output: 120

Using Memoization to Optimize Recursion

Memoization stores previously computed results to avoid redundant calculations, making recursive functions more efficient.

from functools import lru_cache

@lru_cache(maxsize=None)
def fibonacci_memo(n):
    if n <= 0:
        return 0
    elif n == 1:
        return 1
    return fibonacci_memo(n - 1) + fibonacci_memo(n - 2)

print(fibonacci_memo(50))  # Output: 12586269025

When to Use Iteration Instead of Recursion

Recursion is elegant but can be inefficient for large inputs. In such cases, loops are preferable.

Factorial with iteration:

def factorial_iterative(n):
    result = 1
    for i in range(1, n + 1):
        result *= i
    return result

print(factorial_iterative(5))  # Output: 120