Recursive

Recursive describes phenomena that reference themselves or are defined in terms of themselves. In mathematics and computer science, a recursive definition or procedure specifies a base case and a rule for producing larger or more complex instances from smaller ones. Self-reference is central to the concept, but termination must be guaranteed by the base case.

In mathematics, recursive definitions define a sequence or object by base values and a rule that constructs subsequent values from earlier ones. Examples include the natural numbers: 0 is defined as a base case, and each successor n+1 is built from n. Another classic example is the Fibonacci sequence: F0 = 0, F1 = 1, F(n) = F(n-1) + F(n-2).

In computer science, a recursive function calls itself to solve subproblems. Each call passes smaller inputs toward the base case, which returns a result without further recursion. Common examples are factorial and tree traversals. Important considerations include ensuring a base case, avoiding infinite recursion, and sometimes using tail recursion, where the recursive call is the final operation.

Recursion can simplify problem solving and code clarity, especially for divide-and-conquer algorithms and recursive data structures such as trees and linked lists. However, recursive solutions may incur overhead from repeated function calls and risk stack overflow on large inputs. Many problems admit iterative or memoized approaches as alternatives; tail call optimization may help some languages optimize recursion.

Non-termination occurs when no appropriate base case is reached, leading to infinite recursion and eventual program failure. Correct recursive design requires careful specification of base cases, input sizes, and termination guarantees.