Factorial Using Recursion in DSA Java - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is recursion in programming?

Recursion is when a function calls itself to solve smaller parts of a problem until it reaches a simple case it can solve directly.

beginner

What is the base case in a recursive factorial function?

The base case is when the input number is 0 or 1, and the factorial is 1. This stops the recursion from continuing forever.

intermediate

Explain how factorial of 4 is calculated using recursion.

Factorial(4) calls Factorial(3), which calls Factorial(2), then Factorial(1). Factorial(1) returns 1. Then results multiply back: 1 * 2 = 2, 2 * 3 = 6, 6 * 4 = 24.

beginner

What happens if a recursive function does not have a base case?

Without a base case, the function keeps calling itself forever, causing a stack overflow error and crashing the program.

beginner

Write the recursive formula for factorial n!

Factorial(n) = n * Factorial(n - 1), with Factorial(0) = 1 as the base case.

What is the base case for factorial recursion?

A When n is negative

B When n is 2

C When n is 0 or 1

D When n is greater than 10

The base case stops recursion and factorial(0) and factorial(1) both equal 1.

What does factorial(3) return in recursion?

A 6

B 3

C 9

D 1

Factorial(3) = 3 * factorial(2) = 3 * 2 = 6.

What is the risk of missing a base case in recursion?

A Faster execution

B Infinite recursion and crash

C No output

D Correct result

Without a base case, recursion never stops, causing a stack overflow error.

Which of these is the correct recursive call in factorial function?

A factorial(n - 1)

B factorial(n + 1)

C factorial(n * 2)

D factorial(n / 2)

Factorial uses factorial(n - 1) to reduce the problem size step by step.

What is factorial(0)?

A -1

B 0

C Undefined

D 1

By definition, factorial(0) is 1.

Explain how recursion works in calculating factorial with an example.

Think about how the function breaks the problem into smaller parts and then combines answers.

Describe why a base case is important in recursive functions.

Without it, the function would never stop calling itself.

Practice

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

easy

A. The number multiplied by 2

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

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

D. The number divided by 2

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 B

4. Quick Check:

   Factorial = product of integers [OK]

Hint: Factorial multiplies numbers down to 1 [OK]

Common Mistakes:

• Confusing factorial with sum
• Thinking factorial divides the number
• Assuming factorial doubles the number

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

easy

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

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

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

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

Solution

1. Step 1: Identify factorial base case

   Factorial of 0 is defined as 1, so base case returns 1 when n == 0.

2. Step 2: Check options for correct base case

   Only if (n == 0) return 1; returns 1 when n == 0, others return incorrect values.

3. Final Answer:

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

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 n==1 with wrong return value
• Missing base case causing infinite recursion

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

public class Main {
  public static int factorial(int n) {
    if (n == 0) return 1;
    return n * factorial(n - 1);
  }
  public static void main(String[] args) {
    System.out.println(factorial(4));
  }
}

medium

A. 24

B. 10

C. 16

D. 120

Solution

1. Step 1: Trace recursive calls for factorial(4)

   factorial(4) = 4 * factorial(3), factorial(3) = 3 * factorial(2), factorial(2) = 2 * factorial(1), factorial(1) = 1 * factorial(0), factorial(0) = 1.

2. Step 2: Calculate values bottom-up

   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:

• Adding instead of multiplying
• Wrong base case causing wrong output
• Confusing factorial(4) with sum

4. Find the error in this recursive factorial function:

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

medium

A. Return type should be void

B. Missing base case for n == 0

C. Recursive call uses same n causing infinite recursion

D. Multiplication operator is incorrect

Solution

1. Step 1: Analyze recursive call parameter

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

2. Step 2: Identify correct recursive call

   Recursive call should be factorial(n - 1) to reduce n and reach base case.

3. Final Answer:

   Recursive call uses same n causing infinite recursion -> Option C

4. Quick Check:

   Recursive call must reduce n [OK]

Hint: Recursive calls must reduce problem size [OK]

Common Mistakes:

• Calling factorial(n) instead of factorial(n-1)
• Missing base case for n=0
• Wrong return type

5. How would you modify the recursive factorial function to handle negative inputs by returning -1 for any negative number?

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

hard

A. Add if (n < 0) return -1; before base case

B. Change base case to if (n <= 0) return 1;

C. Add if (n == 1) return -1; after base case

D. No change needed; factorial handles negatives

Solution

1. Step 1: Identify handling of negative inputs

   Factorial is undefined for negative numbers, so function should return -1 for n < 0.

2. Step 2: Add condition before base case

   Insert if (n < 0) return -1; before checking base case to catch negatives early.

3. Final Answer:

   Add if (n < 0) return -1; before base case -> Option A

4. Quick Check:

   Negative input returns -1 [OK]

Hint: Check negatives first, return error value [OK]

Common Mistakes:

• Changing base case incorrectly
• Not handling negatives causing infinite recursion
• Assuming factorial works for negatives