QUESTION 39 · Recursion

State the recursive definition of factorial.

2 marks

Answer

For non-negative n, factorial(0) = 1 and factorial(n) = n × factorial(n - 1) when n > 0.

The zero case stops further recursive calls.
Each positive call reduces n by one.

Write and explain a recursive C program to find factorial.

5 marks

Answer in brief

Recursive factorial uses the relationship n! = n × (n - 1)!, with 0! = 1.

Algorithm

Read n and accept values from 0 through 20.
If n <= 1, return 1.
Otherwise, return n multiplied by factorial(n - 1).
Display the returned result.

Call and return trace

For n = 4, the calls ask for factorial(4), factorial(3), factorial(2) and factorial(1). The final call returns 1. The pending multiplications then produce 2 × 1 = 2, 3 × 2 = 6 and 4 × 6 = 24. The original call returns 24 to main.

Why it stops

Every recursive call decreases a supported positive n by one. It eventually reaches 1, which is a base case. Input zero is also handled by the base case. main rejects negative input before converting it to unsigned, preventing an unintended very large unsigned value.

Input and type limits

The result uses unsigned long long and the matching output format %llu. The supported limit 20 ensures that 20! fits the minimum range guaranteed for that type. A wider integer still has a finite range, so recursion cannot calculate arbitrary factorials accurately with this fixed type.

Time complexity

There is one smaller recursive call per level, with constant work apart from the call. The number of levels grows in proportion to n, giving O(n) time in the fixed-width model.

Space complexity

Pending calls wait for smaller results before multiplying. There are O(n) active calls in the usual call-record model, so auxiliary space is O(n). An iterative factorial can perform the same number of multiplications with O(1) auxiliary space.

Flowchart

Control flow for factorial with labelled true and false paths. — Write and explain a recursive C program to find factorial. · Download diagram

C program and output

Download .c Open compiler

/* CodeBhavya | PPS AR25 | Learning example */
#include <stdio.h>
unsigned long long factorial(unsigned int n)
{
    if (n <= 1U) { return 1ULL; }
    return n * factorial(n - 1U);
}
int main(void)
{
    int n;
    if (scanf("%d", &n) != 1 || n < 0 || n > 20) {
        puts("Unsupported input"); return 1;
    }
    printf("Factorial = %llu\n", factorial((unsigned int)n));
    return 0;
}

Sample input and output

Input

Output

Factorial = 24