Основы рекурсии
Часть раздела Основы путешествия по C на Coddy. Урок 50 из 63.
Рекурсия — это метод, при котором функция вызывает сама себя, чтобы решить задачу. Это похоже на решение большой задачи путем разбиения ее на более мелкие аналогичные задачи.
Рассмотрим простую рекурсивную функцию, вычисляющую факториал:
int factorial(int n) {
// Базовый случай: факториал 0 или 1 равен 1
if (n <= 1) {
return 1;
}
// Рекурсивный случай: n! = n * (n-1)!
return n * factorial(n - 1);
}Каждой рекурсивной функции нужны:
- Базовый случай, который останавливает рекурсию
- Рекурсивный случай, который приближает к базовому случаю
Например, вычисление factorial(3):
- factorial(3) вызывает factorial(2)
- factorial(2) вызывает factorial(1)
- factorial(1) возвращает 1 (базовый случай)
- factorial(2) возвращает 2 * 1 = 2
- factorial(3) возвращает 3 * 2 = 6
Задание
ЛегкоСоздай функцию с именем sumToN, которая использует рекурсию для вычисления суммы чисел от 1 до n.
Например:
- sumToN(3) должна вернуть 6 (1 + 2 + 3)
- sumToN(5) должна вернуть 15 (1 + 2 + 3 + 4 + 5)
Твоя функция должна:
- Использовать базовый случай, когда n равно 1 (вернуть 1)
- В противном случае возвращать n плюс сумму чисел от 1 до (n-1)
Попробуйте сами
#include <stdio.h>
// Напишите здесь свою функцию sumToN
// Не изменяйте функцию main()
int main() {
int n;
scanf("%d", &n);
printf("%d", sumToN(n));
return 0;
}В этом уроке есть небольшой тест. Начните урок, чтобы ответить на вопросы и сохранить прогресс.
Все уроки раздела Основы
2Переменные
Типы данныхЦелое числоFloat — DoubleСимволыЛогические значенияКонстантыОсновы printfПравила именования переменныхПреобразование типов, часть 1Преобразование типов, часть 2Итоговое задание на повторение3Операторы
Арифметические операторыОператор остатка от деленияИнкремент/декрементОператоры присваиванияОператоры сравненияЛогические операторы. Часть 1Логические операторы. Часть 2Логические операторы. Часть 3Итоговое заданиеПотренируйтесь самостоятельно: Онлайн-компилятор C