Recursive Factorial

Part of the Logic & Flow section of Coddy's C++ journey — lesson 46 of 56.

The factorial of a number is a perfect example to demonstrate recursion in action. The factorial of n (written as n!) is the product of all positive integers from 1 to n. For example, 5! = 5 × 4 × 3 × 2 × 1 = 120.

What makes factorial ideal for recursion is that it can be defined in terms of itself: n! = n × (n-1)!. This means to calculate 5!, you multiply 5 by 4!, and to calculate 4!, you multiply 4 by 3!, and so on.

Here's how a recursive factorial function looks:

int factorial(int n) {
    if (n <= 1) {           // Base case: 0! and 1! both equal 1
        return 1;
    }
    
    return n * factorial(n - 1);  // Recursive step: n! = n × (n-1)!
}

The base case stops the recursion when n reaches 1 or 0, returning 1. The recursive step multiplies the current number by the factorial of the next smaller number. When you call factorial(4), it calculates 4 × 3 × 2 × 1 by making successive calls until it reaches the base case, then multiplies all the results together as the calls return.

Challenge

Easy

Create a program that implements a recursive factorial function and uses it to calculate factorials for different input values. This challenge will test your understanding of how recursion works by having a function call itself with modified parameters until it reaches a base case.

The following input will be provided:

An integer n representing the number for which to calculate the factorial

Your program should:

Create a recursive function named factorial that takes an integer parameter and returns an integer
The function should implement the base case: if n is less than or equal to 1, return 1
The function should implement the recursive step: return n multiplied by the factorial of n-1
In the main function, read the input value
Call the factorial function with the input value
Print the result using the specified format

Use the following exact output format:

Factorial of [n] is [result]

Remember that the factorial function must call itself with a smaller value each time, moving closer to the base case with each recursive call. The base case prevents infinite recursion by stopping when n reaches 1 or 0. The recursive step multiplies the current number by the factorial of the next smaller number, building up the final result as the function calls return their values.

Cheat sheet

The factorial of n (n!) is the product of all positive integers from 1 to n. It can be defined recursively as: n! = n × (n-1)!

Recursive factorial function:

int factorial(int n) {
    if (n <= 1) {           // Base case: 0! and 1! both equal 1
        return 1;
    }
    
    return n * factorial(n - 1);  // Recursive step: n! = n × (n-1)!
}

The base case stops recursion when n reaches 1 or 0. The recursive step multiplies the current number by the factorial of the next smaller number.

Try it yourself

#include <iostream>
using namespace std;

// TODO: Write your factorial function here

int main() {
    // Read input
    int n;
    cin >> n;
    
    // TODO: Call the factorial function and store the result
    
    // Output the result
    cout << "Factorial of " << n << " is " << result << endl;
    
    return 0;
}