Rekursion

Rekursion, or recursion, is a method in mathematics and computer science in which a function or process refers to itself to solve a problem by solving smaller instances of the same problem. In programming, a recursive function calls itself with a reduced input until a base case is reached.

Recursion can be direct, where a function calls itself, or indirect, through mutual calls between functions. A canonical example is the factorial function: factorial(n) = 1 if n = 0, otherwise n * factorial(n-1). Another is the Fibonacci sequence: fib(n) = fib(n-1) + fib(n-2).

Key concepts include the base case, which terminates the recursion, and the recursive step, which reduces the problem toward that base case. Correctness relies on termination and on eventually reaching the base case. Some languages optimize tail recursion, turning recursive calls into iterative loops to save stack space.

Rekursion is central to many algorithms and data structures. It underpins tree traversals, divide-and-conquer methods, and backtracking. It can simplify design, but may be less efficient than iteration due to call overhead and stack limits. Memoization or converting to iteration are common remedies.

Historically, recursive thinking has roots in mathematical definitions and has become a standard technique in programming since the mid-20th century. Many languages provide clear syntax for recursive definitions, and some offer optimizations such as tail-call optimization.