Рекурсия в Python по шагам: стек вызовов

Рекурсия (задание 16): разбор по шагам

Рекурсивная функция вызывает сама себя. Каждый вызов получает собственный кадр, и они складываются в стек: последний вызванный заканчивается первым.

В задании 16 ЕГЭ функция задана рекуррентно, например F(n) = F(n − 1) + 2·n при n > 1. По шагам видно, как значение собирается при возврате из вызовов.

На что смотреть в пошаговом режиме

• как растёт стек вызовов F(4) → F(3) → F(2) → F(1);
• возврат значений в обратном порядке: сначала F(1), потом F(2) и так далее;
• у каждого кадра своё n — переменные разных вызовов не мешают друг другу.

Код примера

def F(n):
    if n == 1:
        return 1
    return F(n - 1) + 2 * n

def fact(n):
    if n <= 1:
        return 1
    return n * fact(n - 1)

print('F(4) =', F(4))
print('4! =', fact(4))

Код уже в редакторе. Нажмите «По шагам» и листайте шаги кнопкой ▶ или клавишей →. Код можно менять и запускать заново.

Отладчик Python: как пользоваться и частые вопросы