How does recursion work in Python and what are its limitations?

A recursive function calls itself to break a problem into smaller sub-problems of the same kind. Every recursive function needs a base case that stops the recursion and a recursive case that moves toward the base case.

def factorial(n):
    if n <= 1:          # base case
        return 1
    return n * factorial(n - 1)   # recursive case

print(factorial(5))  # 120

# Fibonacci with memoisation to avoid exponential time
from functools import lru_cache

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

print(fib(50))   # runs instantly with caching

Python's default recursion limit is 1000 frames (check with sys.getrecursionlimit(); change with sys.setrecursionlimit(), though increasing it past ~5000 risks a segfault). Exceeding it raises RecursionError. Python does not perform tail-call optimisation — each call adds a frame to the call stack regardless.

For problems where iteration is naturally iterative (Fibonacci, factorial), recursion adds overhead and a stack risk. For inherently recursive structures — trees, nested directories, JSON with arbitrary nesting — recursion is often the clearest approach. When a recursive solution would run into the stack limit, convert to an explicit stack using a list: push children, pop and process.

Invest now in Acorns!!! 🚀
Join Acorns and get your $5 bonus!

Acorns is a micro-investing app that automatically invests your "spare change" from daily purchases into diversified, expert-built portfolios of ETFs. It is designed for beginners, allowing you to start investing with as little as $5. The service automates saving and investing. Disclosure: I may receive a referral bonus.

Invest now!!! Get Free equity stock (US, UK only)!

Use Robinhood app to invest in stocks. It is safe and secure. Use the Referral link to claim your free stock when you sign up!.

The Robinhood app makes it easy to trade stocks, crypto and more.

Webull! Receive free stock by signing up using the link: Webull signup.