Factorial Using Recursion: flowchart, algorithm and program

This program reads a number n and prints n! using a function fact(n) that calls itself. The idea is that n! = n × (n-1)!, so each call hands a smaller problem to the next call until it reaches 0 or 1.

▶ Watch the dry run step by step →

Algorithm

  1. Step 1: Start.
  2. Step 2: Read n.
  3. Step 3: If n == 0 or n == 1, go to step 4; otherwise go to step 5.
  4. Step 4: Set result = 1. Go to step 6.
  5. Step 5: Set result = n * fact(n - 1). Go to step 3.
  6. Step 6: Print factorial of n = result.
  7. Step 7: Stop.

Program in C, Python and Java

Factorial Using Recursion program in C

#include <stdio.h>

long long fact(int n) {
    if (n == 0 || n == 1)
        return 1;
    return n * fact(n - 1);
}

int main() {
    int n;
    printf("Enter n: ");
    scanf("%d", &n);
    printf("Factorial of %d = %lld\n", n, fact(n));
    return 0;
}

Factorial Using Recursion program in Python

def fact(n):
    if n == 0 or n == 1:
        return 1
    return n * fact(n - 1)

n = int(input("Enter n: "))
print("Factorial of", n, "=", fact(n))

Factorial Using Recursion program in Java

import java.util.Scanner;

public class Main {
    static long fact(int n) {
        if (n == 0 || n == 1)
            return 1;
        return n * fact(n - 1);
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        System.out.print("Enter n: ");
        int n = sc.nextInt();
        System.out.println("Factorial of " + n + " = " + fact(n));
    }
}

Sample input: n = 5
Output: Factorial of 5 = 120

How it works

  • The base case is `if (n == 0 || n == 1) return 1;`. Both 0! and 1! equal 1, and this check is what stops the recursion.
  • For any other n, the function returns `n * fact(n - 1)`. It cannot finish the multiplication until the smaller call returns.
  • For n = 5 the calls go down: fact(5) -> fact(4) -> fact(3) -> fact(2) -> fact(1). fact(1) returns 1.
  • The answers then come back up: fact(2) = 2*1 = 2, fact(3) = 3*2 = 6, fact(4) = 4*6 = 24, fact(5) = 5*24 = 120.
  • The result is stored as `long long` and printed with `%lld`, so larger factorials fit than with a plain int.

Dry run (trace table)

StepLineBoxnresultOutput
19Start
212Read n5Enter n:
34n == 0 or n == 1?5
46result = n * fact(n - 1)5
54n == 0 or n == 1?4
66result = n * fact(n - 1)4
74n == 0 or n == 1?3
86result = n * fact(n - 1)3
94n == 0 or n == 1?2
106result = n * fact(n - 1)2
114n == 0 or n == 1?1
125result = 111
136result = n * fact(n - 1)22
146result = n * fact(n - 1)36
156result = n * fact(n - 1)424
166result = n * fact(n - 1)5120
1713Print factorial of n = result5120Factorial of 5 = 120
1814Stop5120

Time and space complexity

Time: O(n) · Space: O(n). The function calls itself n times, each doing constant work, and the call stack grows to depth n.

Common mistakes

  • Leaving out the base case, or writing it wrongly. The function then never stops and the program crashes with a stack overflow.
  • Not handling negative n. fact(-1) never reaches 0 or 1, so it keeps recursing. Check for n < 0 before calling fact.
  • Using `int` as the return type. Factorials grow fast and int overflows at 13!, so use `long long` (which is good up to 20!) and print with `%lld`.

Viva questions

Q1. What is the base case in your fact() function, and why is it needed?

The base case is n == 0 or n == 1, where the function returns 1 directly. Without it the function would keep calling itself forever and the program would crash with a stack overflow.

Q2. Why does fact(0) return 1 and not 0?

By mathematical definition 0! is 1, which is also the empty product. Returning 0 would make every factorial 0 because we multiply by it on the way back.

Q3. Trace fact(4). How do the calls and returns happen?

fact(4) calls fact(3), which calls fact(2), which calls fact(1) and that returns 1. Then the results come back as 2*1=2, 3*2=6 and 4*6=24, so the answer is 24.

Q4. What happens if the user enters a negative number, like -3?

The base case is never reached because n keeps decreasing (-3, -4, -5, ...). The recursion goes on until the stack overflows and the program crashes. We should add a check like if (n < 0) to print an error.

Q5. Why is the return type long long and not int? What does %lld do?

Factorials grow very fast, and int overflows after 12!. long long can hold up to 20! (about 9.2 x 10^18). %lld is the printf format specifier for long long.

Q6. What happens for n = 21 or larger?

21! is larger than the maximum value of long long, so integer overflow occurs and the program prints a wrong (garbage or negative) value. Overflow of signed integers is undefined behaviour in C.

Q7. What is the time and space complexity of this recursive factorial?

Time is O(n) because there are n function calls with one multiplication each. Space is also O(n) because each pending call occupies a stack frame, whereas an iterative loop would use only O(1) space.

Q8. What would change if you wrote this using a loop instead of recursion?

You would start a variable result = 1 and multiply it by i for i from 2 to n. The time stays O(n), but the space drops to O(1) and there is no risk of stack overflow for large n.

Frequently asked questions

What is the base case in recursive factorial?

The base case is n == 0 or n == 1, where the function returns 1 directly. Without it the function would keep calling itself forever.

What is the largest n this program can handle?

With `long long`, n up to 20 works correctly (20! = 2432902008176640000). From 21 onwards the result overflows and prints a wrong value.

Is recursion or a loop better for factorial?

A loop is slightly faster and uses less memory because it makes no extra function calls. Recursion is mainly used here to show how a problem can be defined in terms of a smaller version of itself.

More programs

← All programs

Try AI Flowchart free →