Rekursio

Rekursio, or recursion, is a method of defining objects or solving problems by using themselves as part of the definition or solution. In mathematics and computer science, a recursive definition or algorithm calls itself with a smaller or simpler instance, until a base case is reached. The base case provides a termination condition that prevents infinite descent, while the recursive step reduces the problem to a simpler form.

A canonical example is the factorial function: for nonnegative integers n, n! equals 1 if n is 0, and n! = n × (n−1)! for n > 0. Processing with recursion often mirrors the mathematical principle of induction, and many recursive algorithms perform tasks such as traversing data structures or generating sequences by breaking them down into parts.

Recursive data structures, such as linked lists and trees, are naturally processed with recursive procedures. Mutual recursion occurs when two or more functions are defined in terms of each other. Notation and language features vary, but many languages offer direct support for recursion; some languages optimize tail-recursive calls to reuse stack space.

Applications span software development, formal proof techniques, and areas such as linguistics and artificial intelligence. Limitations include potential exponential time complexity and stack overflows without proper optimization or tail recursion. Etymology: rekursio is the Finnish term for recursion, derived from the broader mathematical concept and closely related to the Latin root.