Recursion: base case and recursive case · Рекурсия: базовый случай и рекурсивный случай
A function that calls itself
- Recursion is when a function calls itself to solve a smaller version of the same problem.
- It needs two parts: a base case that stops, and a recursive case that shrinks the problem.
- Without a base case, it would call itself forever and crash.
Функция, вызывающая саму себя
- Рекурсия — это когда функция вызывает саму себя для решения уменьшенной версии той же задачи.
- Она состоит из двух частей: базового случая, который останавливает процесс, и рекурсивного случая, который уменьшает задачу.
- Без базового случая функция вызывала бы сама себя бесконечно и завершилась ошибкой.
The base case
- The base case is the smallest problem you can answer directly, with no more calls.
- For factorial,
0!and1!are both1— that is the base case. - Always handle the base case first, so the recursion has somewhere to stop.
Базовый случай
- Базовый случай — это самая маленькая задача, которую можно решить напрямую, без дальнейших вызовов.
- Для факториала
0!и1!равны1— это и есть базовый случай. - Всегда обрабатывайте базовый случай первым, чтобы рекурсии было куда остановиться.
The recursive case
- The recursive case solves the problem using the answer to a smaller one.
n! = n × (n - 1)!, sofactorial(n)returnsn * factorial(n - 1).- Each call must move closer to the base case, or it will never stop.
Рекурсивный случай
- Рекурсивный случай решает задачу, используя ответ для более маленькой подзадачи.
n! = n × (n - 1)!, поэтомуfactorial(n)возвращаетn * factorial(n - 1).- Каждый вызов должен приближаться ближе к базовому случаю, иначе он никогда не завершится.
#include <stdio.h>
int factorial(int n) {
if (n <= 1) return 1; // base case
return n * factorial(n - 1); // recursive case
}
int main(void) {
printf("%d\n", factorial(5)); // 120
return 0;
}
Recursion over an array
- You can recurse along an array by passing an index that moves forward each call.
- The base case is "the index has reached the end" (return
0for a sum). - The recursive case is
a[i] + sum(a, i + 1, n)— this item plus the sum of the rest.
Рекурсия по массиву
- Вы можете рекурсивно обходить массив, передавая индекс, который увеличивается при каждом вызове.
- Базовый случай: «индекс достиг конца» (вернуть
0для суммы). - Рекурсивный случай:
a[i] + sum(a, i + 1, n)— этот элемент плюс сумма оставшейся части.
Common mistakes
- Recursion needs a base case, or the call stack overflows.
- Each call must move closer to the base case.
Распространенные ошибки
- Рекурсия требует базового случая, иначе произойдет переполнение стека вызовов.
- Каждый вызов должен приближаться к базовому случаю.
Now you try
- Write the base case first, then the recursive case that calls itself on a smaller input.
- Keep test values small so the numbers stay inside an
int. - Do not write a
main— the checker provides one.
Теперь попробуйте сами
- Сначала напишите базовый случай, а затем рекурсивный случай, который вызывает сам себя для меньшего входа.
- Держите тестовые значения небольшими, чтобы числа помещались в тип данных
int. - Не пишите
main— проверяющая система предоставит его.
Recursion returns up · Рекурсия возвращает результат вверх по стеку вызовов
Calls split to a base case, then values return up. · Вызовы разбиваются до базового случая, затем значения возвращаются вверх.
Complete int factorial(int n) using recursion: return 1 for n <= 1 (the base case), otherwise n * factorial(n - 1). Do not write a main. · Заполните int factorial(int n), используя рекурсию: верните 1 для n <= 1 (базовый случай), иначе верните n * factorial(n - 1). Не пишите main.
Click Run to see the output here. · Нажмите Запустить, чтобы увидеть результат здесь.
Complete int power(int base, int exp) using recursion (assume exp >= 0): base to the power 0 is 1, otherwise base * power(base, exp - 1). Do not write a main. · Заполните int power(int base, int exp), используя рекурсию (предполагается exp >= 0): ⟨base⟩ в степени 0 равно 1, иначе base * power(base, exp - 1). Не пишите ни main.
Click Run to see the output here. · Нажмите Запустить, чтобы увидеть результат здесь.
Complete int array_sum(const int a[], int i, int n) using recursion: it returns the sum of a[i] up to a[n-1]. Base case: i >= n returns 0. Do not write a main. · Дополните int array_sum(const int a[], int i, int n) с использованием рекурсии: она возвращает сумму ⟨a[i]⟩ до ⟨a[n-1]⟩. Базовый случай: i >= n возвращает ⟨0⟩. Не пишите оператор main.
Click Run to see the output here. · Нажмите Запустить, чтобы увидеть результат здесь.