all Python 3Functionsterm

Recursion

recursion

A function calls itself. It needs a base case. The default depth is about 1000 (sys.setrecursionlimit).

Syntax

def f(n):
    if n == 0: return 1
    return n * f(n-1)

Python has no tail-call optimization, so exceeding the depth raises RecursionError rather than hanging silently — for deep cases a loop is safer. If the recursion recomputes the same subproblems (like naive fib), wrap it in functools.lru_cache — that cuts the cost from exponential to linear.

Examples

def factorial(n):
    if n == 0:
        return 1
    return n * factorial(n - 1)
print(factorial(5))  # → 120

def fib(n):
    if n <= 1:
        return n
    return fib(n-1) + fib(n-2)
print(fib(7))  # → 13

def sum_list(lst):
    if not lst:
        return 0
    return lst[0] + sum_list(lst[1:])
print(sum_list([1,2,3,4]))  # → 10

def power(base, exp):
    if exp == 0:
        return 1
    return base * power(base, exp-1)
print(power(2, 10))  # → 1024

import sys
print(sys.getrecursionlimit())  # → 1000
sys.setrecursionlimit(2000)

def count_down(n):
    if n <= 0:
        return
    print(n, end=' ')
    count_down(n-1)
count_down(5)  # → 5 4 3 2 1

def flatten(lst):
    result = []
    for item in lst:
        if isinstance(item, list):
            result.extend(flatten(item))
        else:
            result.append(item)
    return result
print(flatten([1,[2,[3]],4]))  # → [1,2,3,4]

Recursion

Syntax

Examples

See also