C++ Program to Find Factorial Using Recursion

A C++ program to find factorial using recursion defines a function like int factorial(int n) { if (n <= 1) return 1; else return n * factorial(n - 1); } and calls it with the desired number.

Examples

Input0

OutputFactorial of 0 is 1

Input5

OutputFactorial of 5 is 120

Input10

OutputFactorial of 10 is 3628800

How to Think About It

To find the factorial of a number using recursion, think of the problem as multiplying the number by the factorial of the number just before it. Keep doing this until you reach 1, where the factorial is 1 by definition. Use if to stop the recursion at 1 or 0.

Algorithm

1

Get the input number n

2

If n is 0 or 1, return 1 as factorial

3

Otherwise, return n multiplied by factorial of n-1

4

Print the returned factorial value

Code

cpp

#include <iostream>
using namespace std;

int factorial(int n) {
    if (n <= 1) return 1;
    return n * factorial(n - 1);
}

int main() {
    int num = 5;
    cout << "Factorial of " << num << " is " << factorial(num) << endl;
    return 0;
}

Output

Factorial of 5 is 120

Dry Run

Let's trace factorial(5) through the code

1

Call factorial(5)

Since 5 > 1, return 5 * factorial(4)

2

Call factorial(4)

Since 4 > 1, return 4 * factorial(3)

3

Call factorial(3)

Since 3 > 1, return 3 * factorial(2)

4

Call factorial(2)

Since 2 > 1, return 2 * factorial(1)

5

Call factorial(1)

Since 1 <= 1, return 1

6

Return values back up

factorial(2) = 2 * 1 = 2 factorial(3) = 3 * 2 = 6 factorial(4) = 4 * 6 = 24 factorial(5) = 5 * 24 = 120

Call	Return Value
factorial(1)	1
factorial(2)	2
factorial(3)	6
factorial(4)	24
factorial(5)	120

Why This Works

Step 1: Base Case

The function stops calling itself when n is 1 or less, returning 1 to avoid infinite recursion.

Step 2: Recursive Call

For values greater than 1, the function calls itself with n-1 to break down the problem.

Step 3: Multiplying Results

Each call multiplies n by the factorial of n-1, building the final factorial value as calls return.

Alternative Approaches

Iterative approach

cpp

#include <iostream>
using namespace std;

int factorial(int n) {
    int result = 1;
    for (int i = 2; i <= n; i++) {
        result *= i;
    }
    return result;
}

int main() {
    int num = 5;
    cout << "Factorial of " << num << " is " << factorial(num) << endl;
    return 0;
}

This uses a loop instead of recursion, which can be faster and avoids stack overflow for large n.

Using tail recursion

cpp

#include <iostream>
using namespace std;

int factorialHelper(int n, int acc) {
    if (n <= 1) return acc;
    return factorialHelper(n - 1, n * acc);
}

int factorial(int n) {
    return factorialHelper(n, 1);
}

int main() {
    int num = 5;
    cout << "Factorial of " << num << " is " << factorial(num) << endl;
    return 0;
}

Tail recursion can be optimized by some compilers to avoid extra stack use, improving performance.

Complexity: O(n) time, O(n) space

Time Complexity

The function calls itself n times, so the time grows linearly with n.

Space Complexity

Each recursive call adds a new layer to the call stack, so space used is proportional to n.

Which Approach is Fastest?

The iterative approach uses constant space and is generally faster, while recursion is simpler but uses more memory.

Approach	Time	Space	Best For
Recursive	O(n)	O(n)	Simple code, small n
Iterative	O(n)	O(1)	Large n, performance
Tail Recursion	O(n)	O(1) if optimized	When compiler optimizes tail calls