Recursion

Recursion is a method of defining a thing in terms of itself, typically by specifying a base case that terminates the process and a recursive case that reduces the problem to a simpler instance.

In programming, a recursive function calls itself with a smaller input. The base case returns a value without further calls. Each call adds a new frame to the call stack; when the base case is reached, the calls unwind and a final result is produced.

Common examples include factorial, defined with a base case for zero and a recursive step that multiplies by the previous value; the Fibonacci sequence, which can be defined recursively but is inefficient if naïve implemented; and binary search, which divides the problem in half and recurses on the half that contains the target.

Recursion can involve mutual recursion, where two or more functions call each other. Tail recursion is a form where the recursive call is the last operation in the function; some languages optimize tail calls to reuse stack frames, effectively turning recursion into iteration.

Applications include traversals of trees and graphs, parsing, backtracking, and divide-and-conquer algorithms. Recursion often yields clearer and shorter solutions, but can be less efficient than iteration and may risk stack overflow if inputs are large and no tail-call optimization is available.

Recursion is a foundational concept in computer science and mathematics, used to solve problems defined by self-similarity or hierarchical structure through repeated self-application.