Recursion is a technique in programming in which a function calls itself to solve a problem by reducing it to one or more smaller instances of the same problem. Every correct recursive function has a base case that is answered directly and a recursive case that moves the input closer to that base case.
As one of the programming fundamentals, recursion is closely tied to how a function, its parameters and its return value work at run time. It is the natural way to express algorithms on nested or self-similar data, such as trees, directories and grammars, and it is the theoretical counterpart of the loop: anything written with recursion can be written with iteration, and the reverse.
How a recursive function executes
When a function calls itself, the runtime does not reuse the current invocation. It creates a new stack frame that holds the parameters, local variables and the return address of that call. The frames pile up on the call stack until a call reaches the base case and returns a value without calling itself again.
The stack then unwinds: each waiting frame receives the return value of the call it made, completes its own computation and returns to its caller. A classic example is the factorial, defined as factorial(n) = n * factorial(n - 1) with factorial(0) = 1. Computing factorial(4) builds four pending multiplications before the base case lets them collapse into 24.
Correctness rests on three conditions, which together form the usual proof pattern by mathematical induction. The table states each condition and what goes wrong without it.
| Condition | Meaning | Failure if missing |
|---|---|---|
| Base case | At least one input is answered directly | Infinite recursion |
| Progress toward the base case | Each call works on a smaller input | Infinite recursion or cycling |
| Correct combination | Results of subcalls form the right answer | Wrong results despite termination |
Forms of recursion
Recursive functions are classified by how many calls they make and where the call appears. These forms matter because they determine memory use, running time and whether a compiler can optimize the recursion away.
| Form | Structure | Typical example | Note |
|---|---|---|---|
| Linear recursion | One recursive call per invocation | Factorial, list length | Stack depth equals input size |
| Tail recursion | Recursive call is the last operation | Accumulator-based sum | Can be optimized into a loop |
| Binary or tree recursion | Two or more calls per invocation | Naive Fibonacci, tree traversal | Number of calls can grow exponentially |
| Mutual recursion | Functions call each other in a cycle | Even and odd tests, parsers | Harder to trace |
| Divide and conquer | Split input, solve parts, combine | Merge sort, quicksort | Depth often about log2 of input size |
Tail recursion deserves special attention. When nothing remains to be done after the recursive call, the current frame is no longer needed, and a compiler can apply tail call optimization to reuse it. Scheme requires this, and many functional languages provide it, but Python and Java do not, and in JavaScript it is specified yet rarely implemented.
Recursion compared with iteration
Recursion and a loop can express the same computations, but they trade clarity against resource use in different ways. Recursion mirrors the structure of recursive data and recursive definitions, while iteration keeps memory use constant and avoids the overhead of function calls.
| Aspect | Recursion | Iteration |
|---|---|---|
| State storage | Implicit in stack frames | Explicit variables or own stack |
| Memory use | Grows with call depth | Usually constant |
| Fit for nested data | Natural and concise | Requires an explicit stack |
| Risk of failure | Stack overflow at large depth | Infinite loop if the condition is wrong |
| Call overhead | One function call per step | None beyond the loop body |
Any recursive algorithm can be converted into an iterative one by managing an explicit stack in a data structure. This is the standard remedy when input depth is unbounded, for example when traversing a deeply nested document or a very long linked list.
Stack depth, performance and memoization
Each active call consumes stack memory, and the stack is limited. Python sets a default recursion limit of about 1,000 calls, while languages that run on native threads are limited by the thread stack size, commonly between 1 MB and 8 MB depending on the platform. Exceeding the limit raises a RecursionError in Python or a StackOverflowError in Java, or crashes a native program.
Performance problems often come from overlapping subproblems. A naive recursive Fibonacci function recomputes the same values repeatedly and needs an exponential number of calls. Memoization stores each result after its first computation, which reduces the work to a linear number of calls and turns the function into a form of dynamic programming.
The table summarizes the problems that practitioners meet most often when writing recursive code and how they resolve them.
| Problem | Cause | Remedy |
|---|---|---|
| Stack overflow | Depth too large or no base case | Check base case, convert to iteration |
| Exponential running time | Overlapping subproblems recomputed | Apply memoization or bottom-up iteration |
| Base case never reached | Input not reduced, for example off by one | Verify that each call shrinks the input |
| Wrong result at the boundary | Incorrect value for empty input | Test the smallest inputs first |
| Cycles in data | Graph traversed as if it were a tree | Track visited nodes |
A practical rule follows from these limits: use recursion when depth is bounded by a small value, for example by the logarithm of the input or the nesting of real documents, and prefer iteration when depth can grow with the input size.
Understanding it simply
Recursion means solving a big problem by solving a smaller copy of it. You repeat the same step until the problem becomes so small that the answer is obvious.
Imagine counting the people in a long queue without leaving your place. You ask the person behind you how many people stand behind them. They ask the next person, and so on. The last person says zero, because nobody stands behind them. Each answer then travels back, and everyone adds one. In the end you get the total. That last person is the base case that stops the chain.
Applied in practice
A developer writes a tool that calculates how much disk space a project folder uses. A folder can contain files and other folders, which can contain further folders, so the structure is a tree of unknown shape.
The function folder_size(path) adds the size of every file in the folder and, for every subfolder, calls itself and adds the result. A folder with no subfolders is the base case. Because real project folders are rarely nested more than a few dozen levels deep, the call depth stays far below the stack limit.
The recursive version is about a dozen lines long and directly mirrors the folder structure. When the tool is later applied to unusual archives with thousands of nested levels, the developer replaces the recursion with an explicit stack of folders to visit, keeping the same result without any risk of stack overflow.