rekursionen

Rekursionen is a concept in mathematics and computer science describing processes or definitions that refer to themselves. In a recursive definition, a base case provides a simple, non-recursive value, and a recursive clause expresses how to obtain other values from already defined ones. In programming, a function is recursive if it calls itself during execution.

Common forms include structural recursion (defined by the structure of a data type, such as lists or trees) and primitive recursion (a formal notion used in mathematics, where the function is defined from simpler inputs using a base case and a successor operation). General recursion refers to any recursion that may not be constrained to primitive schemes; mutual recursion involves several functions that call each other.

Examples: factorial n! = n × (n-1)!, with base case 0! = 1; Fibonacci sequence F(n) = F(n-1) + F(n-2) with base cases F(0)=0, F(1)=1. Structural recursion appears in tree traversal and list processing; recursive definitions underpin parsing and many algorithms.

Termination and complexity: a well-defined rekursion must terminate; otherwise it may lead to infinite recursion and stack overflow; time complexity often grows with input size; tail recursion can optimize by reusing stack frames.

Applications: algorithms on trees, graph traversals, parsing, and dynamic programming with memoization to avoid recomputation. Rekursion is often simpler to implement and reason about than iterative versions, though it can be less space-efficient without optimization.