C Program for Factorial Using Recursion

A C program to find factorial using recursion defines a function like int factorial(int n) { if (n == 0) return 1; else return n * factorial(n - 1); } and calls it from main() to compute the factorial of a given 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 0, where the factorial is 1 by definition. This way, the function calls itself with smaller numbers until it reaches the base case.

Algorithm

1

Get input number from the user

2

Check if the number is 0; if yes, return 1

3

Otherwise, return the number multiplied by factorial of number minus one

4

Print the result

Code

c

#include <stdio.h>

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

int main() {
    int num = 5;
    printf("Factorial of %d is %d\n", num, factorial(num));
    return 0;
}

Output

Factorial of 5 is 120

Dry Run

Let's trace factorial(5) through the code

1

Call factorial(5)

Since 5 != 0, return 5 * factorial(4)

2

Call factorial(4)

Since 4 != 0, return 4 * factorial(3)

3

Call factorial(3)

Since 3 != 0, return 3 * factorial(2)

4

Call factorial(2)

Since 2 != 0, return 2 * factorial(1)

5

Call factorial(1)

Since 1 != 0, return 1 * factorial(0)

6

Call factorial(0)

Since 0 == 0, return 1

7

Return values back up

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

Function Call	Return Value
factorial(0)	1
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 == 0 and returns 1, which is the factorial of zero.

Step 2: Recursive Call

For any other number, the function calls itself with n - 1 to break the problem into smaller parts.

Step 3: Multiplying Results

Each call multiplies the current number n by the factorial of n - 1, building up the final result.

Alternative Approaches

Iterative approach

c

#include <stdio.h>

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

int main() {
    int num = 5;
    printf("Factorial of %d is %d\n", num, factorial(num));
    return 0;
}

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

Tail recursion

c

#include <stdio.h>

int factorial_helper(int n, int acc) {
    if (n == 0) return acc;
    return factorial_helper(n - 1, n * acc);
}

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

int main() {
    int num = 5;
    printf("Factorial of %d is %d\n", num, factorial(num));
    return 0;
}

Tail recursion can be optimized by some compilers to avoid extra stack usage.

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

Time Complexity

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

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 easier to read but uses more memory.

Approach	Time	Space	Best For
Recursive	O(n)	O(n)	Simple code, small inputs
Iterative	O(n)	O(1)	Large inputs, performance
Tail Recursion	O(n)	O(n) or O(1) if optimized	Compiler-optimized recursion