Рекурсия
Последнее обновление
Рекурсия - это когда функция вызывает саму себя на меньшей версии той же задачи, пока не дойдёт до случая, настолько маленького, что на него можно ответить сразу. Этот сразу решаемый случай и есть базовый случай, и он нужен каждой рекурсивной функции: fib(n) продолжает разбиваться на fib(n - 1) и fib(n - 2), пока не дойдёт до fib(1) или fib(0), которые просто возвращают сами себя. Визуализатор выше делает ровно это: нажмите «воспроизвести» и смотрите, как вызовы ветвятся в дерево, доходят до базовых случаев в листьях, а затем возвращают свои значения наверх, объединяя их на каждом уровне.
Второе, что показывает анимация, это стек вызовов: все вызовы, которые начались, но ещё не вернули результат. Стек растёт по мере углубления вызовов, достигает максимума на глубине рекурсии и разворачивается обратно, когда результаты возвращаются. Именно поэтому глубокая рекурсия может привести к переполнению стека, тогда как итеративный цикл стек вообще не наращивает. Та же форма вызовов лежит в основе поиска в глубину, сортировки слиянием и большинства операций над двоичным деревом.
Временная и пространственная сложность
Для наивной рекурсивной функции Фибоначчи, показанной выше, и двух стандартных способов её починить:
| Подход | Время | Память | Примечания |
|---|---|---|---|
| Наивная рекурсия | O(2^n) | O(n) | Дерево вызовов удваивается на каждом уровне; память определяется самым глубоким стеком, а не всем деревом. |
| С мемоизацией | O(n) | O(n) | Каждое fib(k) вычисляется один раз и кешируется; повторяющиеся поддеревья сводятся к обращению в кеш. |
| Итеративный цикл | O(n) | O(1) | Две скользящие переменные полностью заменяют стек. |
| Любая рекурсия в общем случае | вызовы × работа на вызов | O(max depth) | Стек хранит по одному кадру на каждый вызов, который начался, но ещё не вернулся. |
Шаг за шагом
| Шаг | Что происходит |
|---|---|
| 1 | Первый вызов fib(n) попадает в стек вызовов. |
| 2 | Ему нужен fib(n - 1), поэтому этот вызов тоже попадает в стек; родительский вызов ждёт. |
| 3 | Вызовы вкладываются друг в друга, пока один из них не дойдёт до n <= 1: базовый случай отвечает сразу, без более глубокого вызова. |
| 4 | Значение базового случая возвращается родителю, и тот может начать свой второй вызов, fib(n - 2). |
| 5 | Когда оба дочерних вызова вернулись, родитель складывает их и возвращается сам; его кадр покидает стек. |
| 6 | Возврат повторяется вверх по дереву, пока кадр первого вызова не снимется со стека с итоговым ответом и стек не опустеет. |
Разобранный пример
Вычисление fib(4) в точном порядке вызовов, ровно так, как это проигрывает анимация:
| Вызов | Стек в этот момент | Возвращает |
|---|---|---|
fib(4) | fib(4) | ждёт дочерние вызовы |
fib(3) | fib(4) > fib(3) | ждёт дочерние вызовы |
fib(2) | fib(4) > fib(3) > fib(2) | ждёт дочерние вызовы |
fib(1) | fib(4) > fib(3) > fib(2) > fib(1) | 1 (базовый случай) |
fib(0) | fib(4) > fib(3) > fib(2) > fib(0) | 0 (базовый случай) |
fib(2) объединяет | fib(4) > fib(3) > fib(2) | 1 + 0 = 1 |
fib(1) | fib(4) > fib(3) > fib(1) | 1 (базовый случай) |
fib(3) объединяет | fib(4) > fib(3) | 1 + 1 = 2 |
fib(2) снова | fib(4) > fib(2) | 1, вычислено заново с нуля |
fib(4) объединяет | fib(4) | 2 + 1 = 3 |
Когда использовать рекурсию
| Используйте, когда | Избегайте, когда |
|---|---|
| Задача самоподобна: деревья, вложенные структуры, «разделяй и властвуй» | Простой цикл выражает то же самое без кадров стека |
Глубина ограничена и невелика, например O(log n) в сортировке слиянием | Глубина может дорасти до размера входа на огромных данных, рискуя переполнением стека |
| Поиску с возвратом (бэктрекингу) нужен стек, чтобы помнить, откуда продолжить | Одни и те же подзадачи повторяются, а вы их не кешируете |
| Рекурсивный вариант заметно легче читать и проверять | Вы в горячем цикле, где накладные расходы на вызов ощутимо влияют на скорость |
Код Recursion
Чистая, готовая к запуску реализация Recursion на Python, JavaScript, Java, C++, C. Выберите язык, скопируйте код или откройте его уже загруженным в плейграунде Coddy.
Код Recursion на Python
1calls = 02
3def fib(n, depth=0):4 global calls5 calls += 16 # Print the call with its depth so the recursion is visible7 print(" " * depth + f"fib({n})")8 if n <= 1:9 return n10 return fib(n - 1, depth + 1) + fib(n - 2, depth + 1)11
12
13print("fib(5) =", fib(5))14print("calls made:", calls)Код Recursion на JavaScript
1let calls = 0;2
3function fib(n, depth = 0) {4 calls += 1;5 // Print the call with its depth so the recursion is visible6 console.log(' '.repeat(depth) + `fib(${n})`);7 if (n <= 1) return n;8 return fib(n - 1, depth + 1) + fib(n - 2, depth + 1);9}10
11console.log('fib(5) =', fib(5));12console.log('calls made:', calls);Код Recursion на Java
1public class Main {2 static int calls = 0;3
4 static int fib(int n, int depth) {5 calls++;6 // Print the call with its depth so the recursion is visible7 System.out.println(" ".repeat(depth) + "fib(" + n + ")");8 if (n <= 1) return n;9 return fib(n - 1, depth + 1) + fib(n - 2, depth + 1);10 }11
12 public static void main(String[] args) {13 System.out.println("fib(5) = " + fib(5, 0));14 System.out.println("calls made: " + calls);15 }16}Код Recursion на C++
1#include <iostream>2#include <string>3
4int calls = 0;5
6int fib(int n, int depth) {7 calls++;8 // Print the call with its depth so the recursion is visible9 std::cout << std::string(depth * 2, ' ') << "fib(" << n << ")\n";10 if (n <= 1) return n;11 return fib(n - 1, depth + 1) + fib(n - 2, depth + 1);12}13
14int main() {15 int result = fib(5, 0);16 std::cout << "fib(5) = " << result << "\n";17 std::cout << "calls made: " << calls << "\n";18 return 0;19}Код Recursion на C
1#include <stdio.h>2
3int calls = 0;4
5int fib(int n, int depth) {6 calls++;7 /* Print the call with its depth so the recursion is visible */8 printf("%*sfib(%d)\n", depth * 2, "", n);9 if (n <= 1) return n;10 return fib(n - 1, depth + 1) + fib(n - 2, depth + 1);11}12
13int main(void) {14 printf("fib(5) = %d\n", fib(5, 0));15 printf("calls made: %d\n", calls);16 return 0;17}Часто задаваемые вопросы о рекурсии
Что такое базовый случай в рекурсии?
fib(n) это n <= 1, который сразу возвращает n. Без достижимого базового случая вызовы не прекращаются, стек всё растёт, и программа падает с переполнением стека.Что такое стек вызовов и почему он важен?
n уровней вглубь, занимает O(n) памяти, даже если каждый вызов почти ничего не делает. Ряд плашек под анимацией показывает именно этот стек: как он растёт и как разворачивается обратно.Почему рекурсивный Фибоначчи работает экспоненциальное время?
fib(2) вычисляется внутри fib(4) дважды, и это дублирование примерно удваивается с каждым уровнем, давая O(2^n) вызовов. Кеширование каждого результата при первом вычислении, то есть мемоизация, сжимает дерево до O(n).Рекурсия лучше итерации?
Из-за чего происходит переполнение стека в рекурсивной функции?
Либо базовый случай отсутствует или недостижим, и тогда вызовы не прекращаются, либо рекурсия корректна, но её глубина просто слишком велика для лимита стека среды выполнения, например по одному вызову на элемент при миллионах элементов на входе. Лечится это так: гарантировать базовый случай, ограничить глубину или переписать на итерацию.
Какие алгоритмы естественно рекурсивны?
Связанные ресурсы
Больше визуализаций
