Рекурсия: базовый случай и рекурсивный случай
Метод, который вызывает сам себя
- Рекурсия — это когда метод вызывает сам себя для решения более мелкой части той же задачи.
- На экзамене AP CSA вы в основном трассируете рекурсию (следите за вызовами вручную). Написание небольших рекурсивных методов помогает хорошо трассировать.
- Каждый рекурсивный метод требует двух частей: базового случая и рекурсивного случая.
Базовый случай и рекурсивный случай
- Базовый случай: самый простой входной данные, где вы возвращаете ответ без вызова самого себя. Это останавливает рекурсию.
- Рекурсивный случай: вы вызываете тот же метод с меньшим входным значением, а затем собираете ответ.
- Без базового случая метод вызывает себя бесконечно и крашится (переполнение стека / stack overflow).
Пример: факториал
factorial(n)означаетn * (n-1) * ... * 1. Например,factorial(4) = 24.- Базовый случай:
factorial(1)равен1. - Рекурсивный случай:
factorial(n)являетсяn * factorial(n - 1).
public class Recursion {
public static int factorial(int n) {
if (n <= 1) { // base case
return 1;
}
return n * factorial(n - 1); // recursive case
}
}
Как происходит откат вызовов
- Каждый вызов ожидает завершения меньшего вызова. Затем он выполняет умножение и возвращает результат.
- Проследите за
factorial(3). Вызовы идут вниз, затем ответы возвращаются вверх.
factorial(3) = 3 * factorial(2) <- waits
factorial(2) = 2 * factorial(1) <- waits
factorial(1) = 1 <- base case, returns 1
factorial(2) = 2 * 1 = 2 <- returns 2
factorial(3) = 3 * 2 = 6 <- returns 6
Пример: сумма до n
sumTo(n)добавляет1 + 2 + ... + n. Например, дляsumTo(4) = 10.- Базовый случай:
sumTo(0)равен0(ничего прибавлять не нужно). - Рекурсивный случай:
sumTo(n)являетсяn + sumTo(n - 1).
public class Recursion {
public static int sumTo(int n) {
if (n <= 0) { // base case
return 0;
}
return n + sumTo(n - 1); // recursive case
}
}
Рекурсия по массиву
- Мы также можем использовать рекурсию с индексом, который движется к концу.
- Базовый случай: когда индекс выходит за пределы последнего элемента, верните
0. - Рекурсивный случай: добавьте
a[i]к сумме оставшейся части,arraySum(a, i + 1).
public class Recursion {
public static int arraySum(int[] a, int i) {
if (i >= a.length) { // base case: past the end
return 0;
}
return a[i] + arraySum(a, i + 1);
}
}
- Чтобы просуммировать весь массив, начните с индекса
0:arraySum(a, 0). - Каждый вызов обрабатывает одно значение и доверяет следующий вызов остальной части.
Распространенные ошибки
- Рекурсия требует базового случая, иначе возникнет StackOverflowError.
- Каждый вызов должен приближаться к базовому случаю.
Теперь попробуйте сами
- Каждое задание предоставляет скелет метода с TODO. Напишите базовый случай и рекурсивный случай.
- Скрытый Harness вызывает ваш метод с несколькими значениями и проверяет результат.
- Используйте Check answer (Проверить ответ), чтобы скомпилировать ваш код с предоставленными тестами и посмотреть результаты. Сохраните интерфейс класса и метода, показанный в стартере.
Рекурсия: базовый + рекурсивный случай
Вызовы разделяются до базового случая, затем ответы возвращаются вверх.
Сложность 4/5 · 280 монет + небольшой бонус за первое завершение сегодня
Допишите factorial(int n) так, чтобы она возвращала ⟨n * (n-1) * ... * 1⟩ с помощью рекурсии. Используйте базовый случай для ⟨n <= 1⟩. Проверочная программа тестирует несколько значений.
Нажмите Запустить, чтобы увидеть результат здесь.
Сложность 4/5 · 280 монет + небольшой бонус за первое завершение сегодня
Допишите sumTo(int n) так, чтобы она возвращала ⟨1 + 2 + ... + n⟩ с помощью рекурсии. Используйте базовый случай для ⟨n <= 0⟩. Проверочная программа тестирует несколько значений.
Нажмите Запустить, чтобы увидеть результат здесь.
Сложность 4/5 · 280 монет + небольшой бонус за первое завершение сегодня
Завершите arraySum(int[] a, int i) так, чтобы он возвращал сумму от a[i] до конца, используя рекурсию. Базовый случай: когда i выходит за пределы последнего элемента, верните 0. Проверочный код тестирует несколько массивов.
Нажмите Запустить, чтобы увидеть результат здесь.