rekursion

Recursion

In short: A technique where a function calls itself to solve a problem, by breaking it down into smaller, similar subproblems.

In more detail: Every recursive function needs a base case, which is answered directly with no further recursive call — if this is missing, the function calls itself endlessly, until memory (the stack) overflows. Many recursive solutions can also be implemented iteratively with a loop; recursion is often more elegantly readable, iterative solutions are usually more memory- and performance-efficient.

In Depth

The classic introductory example is factorial (n! = n × (n-1) × (n-2) × ... × 1):

def factorial(n):
    if n <= 1:              # base case - stops the recursion
        return 1
    return n * factorial(n - 1)   # recursive call with a smaller problem
 
factorial(5)  # 5 * factorial(4) = 5 * (4 * factorial(3)) = ... = 120

Every recursive call places a new “stack frame” on the call stack — it remembers where to continue in the code once the deeper call returns its result. For factorial(5), this creates five nested, not-yet-completed calls before the base case is reached and the chain “unwinds” backwards again.

If the base case is missing or never reached (e.g. because the argument doesn’t change in the right direction), this stack grows unbounded — until the available memory is exhausted and the program crashes with a “stack overflow”. This is the recursive sibling of the infinite loop.

Some problems can be solved both recursively and with a loop — both variants of factorial compared:

# Iterative - no additional stack usage
def factorial_iterative(n):
    result = 1
    for i in range(2, n + 1):
        result *= i
    return result

Recursion shines especially for problems that NATURALLY break down into similar subproblems (traversing tree structures, divide-and-conquer algorithms like quicksort, mathematical definitions like the Fibonacci sequence) — there, recursive code is often significantly shorter and closer to the mathematical definition than the iterative variant. For simple, linear repetitions (e.g. “count from 1 to n”), by contrast, a loop is almost always clearer AND more resource-efficient, because it needs no additional stack memory per iteration.

See also: Loops, Algorithms