Back to Study Material Data Structures and Algorithms

Recursion Basics

Recursion is a programming technique where a function solves a problem by calling itself on a smaller version of the same problem. Every recursive solution...

Recursion Basics

How Functions Solve Problems by Calling Themselves

Recursion is a programming technique where a function solves a problem by calling itself on a smaller version of the same problem. Every recursive solution has two essential parts: a base case, which is the simplest version of the problem that can be solved directly without another recursive call, and a recursive case, which breaks the problem down and calls the function again with a smaller input.

Without a base case, a recursive function calls itself forever, eventually exhausting the call stack and causing a stack overflow error. The base case is the stopping condition. For computing the factorial of n, written n!, the base case is factorial(0) equals 1. The recursive case is factorial(n) equals n times factorial(n minus 1). Each call reduces n by one until it reaches zero.

The call stack manages recursive function calls. Each call creates a new frame on the stack containing its local variables and the point to return to when it finishes. When the base case is reached, the stack unwinds: frames are popped and return values propagate back up through the chain of callers. For factorial(5), the stack grows to depth five before unwinding.

Recursion is natural for problems that have a recursive structure. Tree traversal, divide-and-conquer sorting, and many combinatorial problems are expressed more cleanly with recursion than with loops. The Tower of Hanoi, a puzzle involving moving disks between pegs, has an elegant three-line recursive solution that would require complex state management to implement iteratively.

The time complexity of a recursive algorithm is found by analyzing how many recursive calls are made and how much work is done per call. The recurrence relation T(n) equals 2T(n/2) plus O(n) describes merge sort: two recursive calls each on half the input, plus O(n) work to merge. Solving this recurrence with the Master Theorem gives T(n) equals O(n log n).

Recursion has costs: each function call has overhead, and deep recursion uses O(depth) stack space. For problems with thousands of levels of recursion, an iterative solution with an explicit stack is safer and faster.

Worked example: computing the nth Fibonacci number recursively. fib(n) returns fib(n-1) plus fib(n-2), with base cases fib(0) equals 0 and fib(1) equals 1. The naive recursive version is O(2^n) because it recomputes subproblems repeatedly. Adding memoization reduces it to O(n).

Interview tip: whenever you write a recursive function, identify the base case first and verify it is reachable from the recursive case. Then trace through a small example by hand to ensure the recursion terminates correctly.