все Python 3Функциипонятие

Рекурсия

рекурсия

Функция вызывает себя. Требует базовый случай. Глубина по умолчанию ~1000 (sys.setrecursionlimit).

Синтаксис

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

У Python нет оптимизации хвостовой рекурсии, поэтому превышение глубины даёт RecursionError, а не тихое зависание — для глубоких случаев надёжнее цикл. Если рекурсия перевычисляет одни и те же подзадачи (как наивный fib), оберни её в functools.lru_cache — сложность падает с экспоненциальной до линейной.

Примеры

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]

См. также

Открыть в полном глоссарииdocs.python.orgСообщить о неточности