How do I write recursive functions in Python?

Short answer

A recursive function calls itself to solve smaller instances of the same problem. Every recursive function needs a base case to terminate and a recursive case that moves toward the base case.

Steps

1. Identify the base case (the simplest input that can be solved directly).
2. Define the recursive case that breaks the problem into smaller pieces.
3. Combine the results.

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

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

print(factorial(5))      # 120
print(fibonacci(30))     # 832040

Tips

• Memoization (caching) prevents exponential recomputation in recursive algorithms.
• Python has a default recursion limit of 1000; increase it with sys.setrecursionlimit() only if necessary.
• Iterative solutions are often more memory-efficient in Python because tail-call optimization is not performed.
• Use functools.lru_cache to add memoization with a decorator.

Common issues

• Missing or incorrect base cases cause infinite recursion and a RecursionError.
• Deep recursion consumes the C stack and can crash the interpreter.
• Mutable default arguments used as memo dictionaries can leak state across calls.