Recursion is a method of defining a structure or performing a computation by referring to instances of the same structure or computation. In computer science, a recursive procedure invokes itself directly or indirectly, usually to solve smaller subproblems whose results contribute to the original answer. In mathematics, recursive definitions specify objects through initial cases and rules for constructing subsequent cases. Recursion is therefore both a descriptive technique and a practical basis for designing an algorithm. (sicp.sourceacademy.org)
Definitions and base cases
A terminating recursive computation typically has two components: base cases, which produce answers without further recursive calls, and recursive cases, which reduce the problem to other instances. The reduction need not decrease a numerical argument; it may shorten a sequence, remove a component, or descend into a smaller part of a structure. What matters is progress toward a case that can be handled directly. (ocw.mit.edu)
For example, the function called factorial can be defined for a nonnegative integer (n) by
[ 0!=1,\qquad n!=n(n-1)!\quad(n>0). ]
The corresponding pseudocode is:
factorial(n):
require n is a nonnegative integer
if n = 0:
return 1
return n * factorial(n - 1)
To evaluate factorial(3), the procedure requests factorial(2), then factorial(1), then factorial(0). Returning from those calls supplies the values needed to obtain (6). The input restriction is important: repeatedly subtracting one from a negative integer would never reach zero. (ocw.mit.edu)
Direct recursion occurs when a procedure calls itself. Indirect, or mutual, recursion occurs when a chain of calls eventually returns to the original procedure. The defining feature is this circular relationship among procedure definitions, rather than any particular number of calls. (sicp.sourceacademy.org)
Termination and correctness
The presence of a base case alone does not establish termination. Recursive calls must eventually reach it. A common termination argument identifies a nonnegative measure that strictly decreases with each call, such as the number of unprocessed elements. For factorial, that measure is (n). For operations on finite structures, it may be the size of the remaining structure. An unchanged or improperly reduced input can prevent termination. (ocw.mit.edu)
Correctness is closely connected to mathematical induction. A proof establishes that the base cases return correct answers, then shows that correct answers to smaller instances imply a correct answer to the larger instance. Recursive definitions construct or compute objects; induction establishes properties of those objects. The two techniques share a base-and-step organization but serve different purposes. (cs.cornell.edu)
Execution and memory
Many implementations manage recursive execution using a call stack. Each active invocation has a frame containing information needed to continue execution, including local state and a return location. A recursive call adds another active invocation; a return allows its caller to resume. In ordinary recursive factorial, callers retain pending multiplications until the innermost call finishes. (sicp.sourceacademy.org)
Memory consumption depends on the maximum number of simultaneously active calls, not simply the total number of calls made. Deep recursion can exhaust available stack space. Moreover, local objects and copied inputs may consume additional memory beyond the frames themselves. These costs depend on the procedure and the programming language implementation. (ocw.mit.edu)
Recursion, iteration, and tail calls
Iteration expresses repetition through successive state updates, commonly using loops. Recursion and iteration can describe equivalent computations, but their source-code forms do not necessarily determine their memory behavior. A recursive procedure may generate a process whose complete state consists of only a fixed collection of variables. (sicp.sourceacademy.org)
A tail call is a call whose result can be returned without further computation by its caller. In tail-recursive factorial, an accumulator holds the product already computed, and the recursive call receives the updated accumulator. The earlier factorial example is not tail-recursive because multiplication remains after the recursive call returns. An implementation supporting proper tail calls can avoid retaining an expanding chain of frames. Tail-recursive syntax alone does not guarantee that optimization. (sicp.sourceacademy.org)
Complexity and repeated subproblems
The computational complexity of a recursive algorithm depends on its call structure and the work performed within each invocation. Using asymptotic notation, ordinary recursive factorial takes (O(n)) operations and (O(n)) stack space under a constant-cost arithmetic model. A recurrence relation such as (T(n)=T(n-1)+O(1)) expresses its running time. Costs differ when arithmetic on increasingly large integers is counted explicitly. (cs.cornell.edu)
A straightforward recursive computation of the Fibonacci sequence, using (F(n)=F(n-1)+F(n-2)), repeatedly evaluates the same smaller instances. Its operation count grows exponentially, although its maximum call depth grows linearly. This distinction separates total computational work from simultaneous storage requirements. (sicp.sourceacademy.org)
When a computation contains overlapping subproblems, memoization stores previously computed results for reuse. Applied to Fibonacci, it reduces the number of distinct computed instances to a linear quantity. This reuse is central to dynamic programming; the inefficiency of naive Fibonacci recursion comes from repeated work, not from self-calls alone. (cs.cornell.edu)
Recursive structures and applications
Recursion naturally matches hierarchical data structures. A tree, for example, contains subtrees that can be processed using the same operation as the whole tree. Recursive procedures can combine the results from these subtrees, making their organization follow the structure of the data. Circular references require additional care: following them without a stopping mechanism may continue indefinitely. (sicp.sourceacademy.org)
Divide-and-conquer algorithms likewise reduce a problem to smaller instances and combine their answers. Recursion provides a direct way to express this organization, while complexity analysis determines whether the decomposition actually yields an efficient computation. (ocw.mit.edu)