Рекурсия
| 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) раскручивается от базового случая вверх
fact(0) возвращает 1 (базовый случай); каждый родитель умножает: 1, 1, 2, 6.
Рекурсивный метод — это тот, который...
Рекурсия = метод, вызывающий сам себя.
Базовый случай — это...
Базовый случай останавливает рекурсию.
Рекурсия без достижимого базового случая вызывает...
Она рекурсивно выполняется бесконечно, пока стек не переполнится.
Рекурсивный случай должен вызывать сам себя для...
Каждый вызов должен сокращаться к базовому случаю.
Если factorial(0)=1 и factorial(n)=n*factorial(n-1), чему равен factorial(3)?
3 * 2 * 1 * 1 = 6.
Каждый рекурсивный вызов сохраняет собственную копию своих параметров до возврата.
Вызовы стека независимо, затем происходит раскрутка.