Python / Core Python Fundamentals Interview Questions
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.
More Related questions...
