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

Часть раздела Основы путешествия по C на Coddy. Урок 50 из 63.

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

Рассмотрим простую рекурсивную function, вычисляющую factorial:

int factorial(int n) {
    // Базовый случай: факториал 0 или 1 равен 1
    if (n <= 1) {
        return 1;
    }
    
    // Рекурсивный случай: n! = n * (n-1)!
    return n * factorial(n - 1);
}

Каждая рекурсивная function требует:

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

Например, вычисление 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 (return 1)
В противном случае возвращать n плюс сумму чисел от 1 до (n-1)

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

#include <stdio.h>

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

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