Задачи на рекурсию с решениями

Рекурсия — когда функция вызывает саму себя. Главное — базовый случай, где вызовы останавливаются.

Факториал рекурсией

Факториал: n! = n × (n−1)!. Базовый случай — 0! = 1, на нём рекурсия останавливается.

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

Сумма до n

Сумма чисел от 1 до n тоже раскладывается: sum(n) = n + sum(n−1), база — sum(0) = 0.

def s(n):
    if n == 0:
        return 0
    return n + s(n - 1)
print(s(5))   # 15

Числа Фибоначчи

Фибоначчи: f(n) = f(n−1) + f(n−2), базовые случаи — f(0)=0 и f(1)=1. Наглядно, но для больших n лучше цикл — рекурсия тут медленная.

def fib(n):
    if n < 2:
        return n
    return fib(n - 1) + fib(n - 2)

Частые вопросы

Что будет без базового случая? Бесконечная рекурсия и ошибка RecursionError.

Рекурсия или цикл? Для простых задач цикл быстрее; рекурсия удобна для «ветвящихся» задач.