Основы рекурсии

Часть раздела Fundamentals путешествия по 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)

Шпаргалка

Рекурсия — это метод, при котором функция вызывает саму себя для решения задачи путем ее разбиения на более мелкие, аналогичные подзадачи.

Каждой рекурсивной функции необходимы:

Базовый случай для остановки рекурсии
Рекурсивный случай, который приближает выполнение к базовому случаю

Пример — функция вычисления факториала:

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

Попробуйте сами

#include <stdio.h>

// Напишите здесь вашу функцию sumToN

// Не изменяйте функцию main()
int main() {
    int n;
    scanf("%d", &n);
    
    printf("%d", sumToN(n));
    return 0;
}