Рекурсия
Введено
13:31
Data Collections (Наборы данных)
Сделайте одно фото на телефоне. Для компьютера это вовсе не картинка — это сетка чисел, по одному на каждый пиксель, около двенадцати миллионов из них. Попробуйте теперь…
Озвучивание на английском · переключаемые субтитры на английском и китайском языках
In this lesson
| English | Значение |
|---|---|
| Recursion/rɪˈkɜːʃn/ | рекурсия |
| base case/beɪs keɪs/ | базовый случай |
| recursive case/rɪˈkɜːsɪv keɪs/ | рекурсивный случай |
| unwind/ʌnˈwaɪnd/ | откат |
Метод, вызывающий сам себя
- Рекурсия — это когда метод вызывает сам себя для решения уменьшенной версии той же задачи.
- Каждая рекурсия состоит из двух частей: базового случая и рекурсивного случая.
- Базовый случай останавливает рекурсию — маленький входной параметр, который метод обрабатывает напрямую.
- Рекурсивный случай вызывает метод снова для меньшего входного параметра.
Базовый случай
- Без базового случая метод вызывает себя навек — это
StackOverflowError. - Базовый случай обрабатывает самый маленький вход без дополнительного вызова.
- Пример:
factorial(0)возвращает1напрямую — больше вызовов нет. - Всегда проверяйте: достигает ли каждый путь в итоге базового случая?

Сортировка слиянием рекурсивно делит на две половины, затем объединяет отсортированные части
Рекурсивный случай
- Рекурсивный случай выполняет небольшую работу, затем вызывает сам себя для меньшего входа.
factorial(n)возвращаетn * factorial(n - 1)— вход уменьшается на единицу при каждом вызове.- Каждый вызов ожидает возврата меньшего вызова перед завершением.
- Вызовы накапливаются стеком, достигают базового случая, затем разворачиваются обратно к верху.
Как накапливается стек вызовов
factorial(3)→3 * factorial(2)→3 * (2 * factorial(1))→3 * (2 * (1 * factorial(0))).factorial(0)возвращает1; затем стек разворачивается:1, 1, 2, 6.- Каждый вызов хранит свою собственную копию параметров до момента возврата.
- Трассировка рекурсии означает отслеживание вызовов вниз, затем возвратов вверх.
Каждая рекурсия требует базового случая, который её останавливает — и каждый рекурсивный вызов должен двигаться К этому базовому случаю (меньший вход). Пропустите базовый случай или передайте тот же или больший вход, и метод будет рекурсировать бесконечно до появления StackOverflowError. Трассируйте, отслеживая вызовы вниз до базового случая, а затем возвраты вверх.
sum(n) = 1 + 2 + … + n через рекурсию:
- Базовый случай:
if (n == 0) return 0; - Рекурсивный случай:
return n + sum(n - 1); sum(3)→3 + sum(2)→3 + (2 + sum(1))→ … →6.
Рекурсия — это метод, вызывающий сам себя для меньшего входа. Ей нужен базовый случай (останавливается напрямую, без дальнейших вызовов) и рекурсивный случай (выполняет немного работы, затем рекурсирует для меньшего входа). Вызовы накапливаются стеком вниз до базового случая, затем разворачиваются обратно вверх. Пропустите базовый случай, и вы получите StackOverflowError.
factorial(3) unwinds from the base case up
fact(0) returns 1 (base case); each parent multiplies: 1, 1, 2, 6.
A recursive method is one that...
Сложность 1/5 · 100 монет + небольшой бонус за первое завершение сегодня
Recursion = a method calling itself.
The base case is...
Сложность 1/5 · 100 монет + небольшой бонус за первое завершение сегодня
The base case stops the recursion.
A recursion with no reachable base case causes...
Сложность 1/5 · 100 монет + небольшой бонус за первое завершение сегодня
It recurses forever until the stack overflows.
The recursive case must call itself on...
Сложность 1/5 · 100 монет + небольшой бонус за первое завершение сегодня
Each call must shrink toward the base case.
If factorial(0)=1 and factorial(n)=n*factorial(n-1), what is factorial(3)?
Сложность 2/5 · 140 монет + небольшой бонус за первое завершение сегодня
3 * 2 * 1 * 1 = 6.
Each recursive call keeps its own copy of its parameters until it returns.
Сложность 1/5 · 100 монет + небольшой бонус за первое завершение сегодня
Calls stack independently, then unwind.