Recursion
DSA · Introduction to DSA
Theory
Recursion is when a function solves a problem by calling itself on a smaller version of the same problem. Every recursive function needs a base case that stops the calls and a recursive case that moves towards the base case. Each call is placed on the call stack until it returns, so deep recursion uses O(depth) memory. Many structures, such as trees and nested folders, are naturally recursive.
Why we use it
Recursion expresses divide-and-conquer, tree traversal and backtracking very clearly, often in a few lines where a loop would need an explicit stack.
When to use it
Use recursion for trees, graphs (DFS), divide and conquer (merge sort, quick sort), backtracking and problems defined in terms of smaller sub-problems. Prefer loops when depth could be very large, because Python limits recursion depth to about 1000.
How it works
- Call f(n)
- Is n a base case? Yes: Return the base value. No: Call f(smaller n).
- Wait for the smaller call to return
- Combine its result with the current step
- Return the result to the caller
Syntax
def solve(problem):
if problem is small enough: # base case
return direct answer
smaller = shrink(problem) # recursive case
return combine(solve(smaller))Example
def factorial(n):
if n <= 1: # base case
return 1
return n * factorial(n - 1)
def sum_digits(n):
if n < 10:
return n
return n % 10 + sum_digits(n // 10)
print("5! =", factorial(5))
print("Sum of digits of 98765 =", sum_digits(98765))Key points
- Always define a base case first
- Each call must make the problem smaller
- Recursion depth costs stack memory
- Any recursion can be rewritten with a loop and an explicit stack