Factorial Using Recursion in DSA C - Build from Scratch

Factorial Using Recursion

📖 Scenario: Imagine you want to calculate the factorial of a number, which is the product of all positive integers up to that number. For example, factorial of 5 is 5 x 4 x 3 x 2 x 1 = 120.Using recursion, a function can call itself to solve smaller parts of the problem until it reaches the simplest case.

🎯 Goal: You will build a C program that calculates the factorial of a given number using a recursive function.

📋 What You'll Learn

Create a recursive function called factorial that takes an integer n and returns the factorial of n.

Use a base case in the recursion where factorial of 0 is 1.

Call the factorial function with the number 5 and store the result.

Print the result in the format: Factorial of 5 is 120.

💡 Why This Matters

🌍 Real World

Calculating factorial is useful in mathematics, statistics, and computer science problems like permutations and combinations.

💼 Career

Understanding recursion is fundamental for many programming tasks and technical interviews.

1

Create the main function and declare the number

Write a main function and declare an integer variable called number with the value 5.

DSA C

int main() {
    // Your code here
}

Hint

The main function is the starting point of a C program. Declare int number = 5; inside it.

2

Write the recursive factorial function

Write a recursive function called factorial that takes an integer n and returns an integer. Use the base case: if n == 0, return 1. Otherwise, return n * factorial(n - 1).

DSA C

int main() {
    int number = 5;
    return 0;
}

// Your code here

Hint

The function calls itself with n - 1 until it reaches 0, then returns 1.

3

Call the factorial function and store the result

Inside the main function, call factorial(number) and store the result in an integer variable called result.

DSA C

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

int main() {
    int number = 5;
    // Your code here
    return 0;
}

Hint

Store the factorial of number in result by calling factorial(number).

4

Print the factorial result

Add a printf statement inside main to print: Factorial of 5 is 120 using the variables number and result.

DSA C

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

int main() {
    int number = 5;
    int result = factorial(number);
    // Your code here
    return 0;
}

Hint

Use printf("Factorial of %d is %d\n", number, result); to print the output.

Practice

1. What does the factorial of a number represent in mathematics?

easy

A. The number divided by 2

B. The sum of all positive integers up to that number

C. The number multiplied by 2

D. The product of all positive integers up to that number

Solution

1. Step 1: Understand factorial definition

   Factorial of a number n (written as n!) is the product of all positive integers from 1 to n.

2. Step 2: Compare options with definition

   Only The product of all positive integers up to that number correctly describes factorial as a product, not sum or division.

3. Final Answer:

   The product of all positive integers up to that number -> Option D

4. Quick Check:

   Factorial = product of integers [OK]

Hint: Factorial means multiply all numbers down to 1 [OK]

Common Mistakes:

• Confusing factorial with sum
• Thinking factorial divides the number
• Mixing multiplication with addition

2. Which of the following is the correct base case for a recursive factorial function in C?

easy

A. if (n == 0) return 1;

B. if (n == 1) return 0;

C. if (n == 0) return 0;

D. if (n == 1) return n + 1;

Solution

1. Step 1: Identify base case for factorial

   Factorial of 0 is defined as 1, so base case must return 1 when n is 0.

2. Step 2: Check options for correct base case

   if (n == 0) return 1; returns 1 when n is 0, which is correct. Others return wrong values or conditions.

3. Final Answer:

   if (n == 0) return 1; -> Option A

4. Quick Check:

   Base case n=0 returns 1 [OK]

Hint: Base case for factorial is n=0 returns 1 [OK]

Common Mistakes:

• Returning 0 for base case
• Using wrong condition like n==1
• Returning n+1 incorrectly

3. What is the output of the following C code?

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

int main() {
    printf("%d", factorial(4));
    return 0;
}

medium

A. 24

B. 10

C. 16

D. 120

Solution

1. Step 1: Trace factorial(4) calls

   factorial(4) calls factorial(3), factorial(3) calls factorial(2), factorial(2) calls factorial(1), factorial(1) calls factorial(0).

2. Step 2: Calculate return values

   factorial(0) = 1
   factorial(1) = 1 * 1 = 1
   factorial(2) = 2 * 1 = 2
   factorial(3) = 3 * 2 = 6
   factorial(4) = 4 * 6 = 24

3. Final Answer:

   24 -> Option A

4. Quick Check:

   4! = 24 [OK]

Hint: Multiply down from n to 1 recursively [OK]

Common Mistakes:

• Stopping recursion too early
• Adding instead of multiplying
• Wrong base case causing infinite recursion

4. Identify the error in this recursive factorial function and select the fix:

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

medium

A. Change base case to if (n == 0) return 0;

B. Change recursive call to factorial(n - 1);

C. Remove base case entirely;

D. Change return to n + factorial(n - 1);

Solution

1. Step 1: Analyze recursive call

   The function calls factorial(n) inside itself without reducing n, causing infinite recursion.

2. Step 2: Correct recursive call to reduce n

   Changing call to factorial(n - 1) ensures n decreases each call, reaching base case.

3. Final Answer:

   Change recursive call to factorial(n - 1); -> Option B

4. Quick Check:

   Recursive call must reduce n [OK]

Hint: Recursive calls must move toward base case [OK]

Common Mistakes:

• Calling factorial(n) again causing infinite loop
• Wrong base case value
• Using addition instead of multiplication

5. How would you modify a recursive factorial function to handle negative inputs by returning -1 for invalid input?
Choose the correct code snippet.

hard

A. if (n <= 0) return 1; else return n * factorial(n - 1);

B. if (n == 0) return -1; else return n * factorial(n - 1);

C. if (n < 0) return -1; else if (n == 0) return 1; else return n * factorial(n - 1);

D. if (n < 0) return 0; else return n * factorial(n - 1);

Solution

1. Step 1: Add check for negative input

   Factorial is not defined for negative numbers, so return -1 if n < 0.

2. Step 2: Keep base case and recursive call correct

   Return 1 if n == 0, else multiply n by factorial(n - 1).

3. Final Answer:

   if (n < 0) return -1; else if (n == 0) return 1; else return n * factorial(n - 1); -> Option C

4. Quick Check:

   Negative input returns -1 [OK]

Hint: Check negative input first, then proceed [OK]

Common Mistakes:

• Not handling negative input
• Returning wrong value for negatives
• Incorrect base case for zero