rekursija

Rekursija is a method of solving problems by repeatedly applying the same procedure to smaller instances of the same problem. In rekursija, a function or process calls itself, typically with a simpler input, and stops when a base case is reached. Each recursive step reduces the problem toward that base case.

The term originates from Latin recursio and is widely used in mathematics and computer science. In rekursija, every non-base call should move toward the base case, ensuring termination. Properly formed recursive definitions express a problem in terms of itself plus auxiliary information.

A classic example is the factorial function. For a non-negative integer n, factorial(n) is defined as 1 if n is 0, otherwise n × factorial(n−1). The base case provides a stopping condition, while the recursive case reduces the problem size. The Fibonacci sequence is another common example, defined so that each term depends on earlier terms.

Advantages of rekursija include concise, natural representations of hierarchical and divide-and-conquer problems, such as tree traversals and recursive data structures. Disadvantages include potential high memory usage from the call stack and the risk of infinite recursion if the base case is missing or not approached properly. Techniques like tail recursion and memoization can mitigate these issues, with tail-recursive functions often allowing compiler optimizations in many languages.

In programming, rekursija is closely related to recursive data structures (such as lists and trees) and to algorithms that solve problems by breaking them into smaller instances. It is contrasted with iteration, which repeats steps in loops rather than by self-referential calls. Rekursija also appears in fields such as linguistics, mathematics, and fractal geometry.