Рекурсия
Последнее обновление
Рекурсия - это когда функция вызывает саму себя на меньшей версии той же задачи, пока не дойдёт до случая, настолько маленького, что на него можно ответить сразу. Этот сразу решаемый случай и есть базовый случай, и он нужен каждой рекурсивной функции: 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
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
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
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++
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
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).Рекурсия лучше итерации?
Ни то, ни другое не лучше всегда. Любую рекурсию можно переписать как цикл с явным стеком, а любой цикл, как рекурсию. Рекурсия выигрывает в читаемости на самоподобных задачах вроде обхода дерева и поиска в глубину; итерация выигрывает по памяти и накладным расходам на вызовы на линейных проходах.
Из-за чего происходит переполнение стека в рекурсивной функции?
Либо базовый случай отсутствует или недостижим, и тогда вызовы не прекращаются, либо рекурсия корректна, но её глубина просто слишком велика для лимита стека среды выполнения, например по одному вызову на элемент при миллионах элементов на входе. Лечится это так: гарантировать базовый случай, ограничить глубину или переписать на итерацию.
Какие алгоритмы естественно рекурсивны?
Сортировки по принципу «разделяй и властвуй», такие как сортировка слиянием и quicksort, обходы двоичного дерева и графов, бинарный поиск, задачи с возвратом вроде расстановки N ферзей, а также всё, что определено над вложенной структурой: JSON, файловая система и подобное.
Связанные ресурсы
Больше визуализаций
