Рекурсивный факториал

Часть раздела Логика и управление потоком путешествия по C++ на Coddy — урок 46 из 56.

Факториал числа — это отличный пример для демонстрации рекурсии в действии. Факториал n (записывается как n!) — это произведение всех положительных целых чисел от 1 до n. Например, 5! = 5 × 4 × 3 × 2 × 1 = 120.

Что делает факториал идеальным для рекурсии, так это то, что его можно определить через самого себя: n! = n × (n-1)!. Это означает, что для вычисления 5! вы умножаете 5 на 4!, а для вычисления 4! вы умножаете 4 на 3! и так далее.

Вот как выглядит рекурсивная функция факториала:

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

Базовый случай останавливает рекурсию, когда n достигает 1 или 0, возвращая 1. Рекурсивный шаг умножает текущее число на факториал следующего меньшего числа. Когда вы вызываете factorial(4), он вычисляет 4 × 3 × 2 × 1, выполняя последовательные вызовы до тех пор, пока не достигнет базового случая, а затем перемножает все результаты по мере возврата вызовов.

Задание

Легко

Создайте программу, которая реализует рекурсивную функцию факториала и использует ее для вычисления факториалов различных входных значений. Эта задача проверит ваше понимание того, как работает рекурсия, заставляя функцию вызывать саму себя с измененными параметрами до тех пор, пока она не достигнет базового случая.

Будут предоставлены следующие входные данные:

Целое число n, представляющее число, для которого необходимо вычислить факториал

Ваша программа должна:

Создать рекурсивную функцию с именем factorial, которая принимает целочисленный параметр и возвращает целое число
Функция должна реализовывать базовый случай: если n меньше или равно 1, вернуть 1
Функция должна реализовывать рекурсивный шаг: вернуть n, умноженное на факториал n-1
В главной функции прочитать входное значение
Вызвать функцию factorial с входным значением
Вывести результат, используя указанный формат

Используйте следующий точный формат вывода:

Factorial of [n] is [result]

Помните, что функция факториала должна вызывать саму себя с меньшим значением каждый раз, приближаясь к базовому случаю с каждым рекурсивным вызовом. Базовый случай предотвращает бесконечную рекурсию, останавливаясь, когда n достигает 1 или 0. Рекурсивный шаг умножает текущее число на факториал следующего меньшего числа, формируя окончательный результат по мере того, как вызовы функций возвращают свои значения.

Шпаргалка

Факториал числа n (n!) — это произведение всех положительных целых чисел от 1 до n. Его можно определить рекурсивно как: n! = n × (n-1)!

Рекурсивная функция факториала:

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

Базовый случай останавливает рекурсию, когда n достигает 1 или 0. Рекурсивный шаг умножает текущее число на факториал следующего меньшего числа.

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

#include <iostream>
using namespace std;

// TODO: Напишите вашу функцию факториала здесь

int main() {
    // Чтение входных данных
    int n;
    cin >> n;
    
    // TODO: Вызовите функцию факториала и сохраните результат
    
    // Вывод результата
    cout << "Factorial of " << n << " is " << result << endl;
    
    return 0;
}