Factorial Using Recursion in DSA Go - 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 factorial of 5 (5!)?

5! = 5 × 4 × 3 × 2 × 1 = 120

beginner

What is the base case in factorial recursion?

The base case is when n = 0, and factorial(0) = 1. This stops the recursion from continuing forever.

intermediate

How does the recursive factorial function calculate factorial(n)?

It calculates factorial(n) by multiplying n with factorial(n-1), breaking the problem into smaller parts until it reaches the base case.

intermediate

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

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

What is the base case for factorial recursion?

A factorial(0) = 1

B factorial(1) = 0

C factorial(n) = n * factorial(n+1)

D factorial(n) = n + factorial(n-1)

The base case stops recursion. For factorial, factorial(0) = 1 is the base case.

What does factorial(3) equal?

A 1

B 9

C 3

D 6

factorial(3) = 3 × 2 × 1 = 6

In recursion, what is the function doing when it calls itself?

A Breaking the problem into smaller parts

B Ending the program

C Ignoring the problem

D Running an infinite loop

Recursion solves problems by breaking them into smaller parts using self-calls.

What will happen if the base case is missing in a recursive factorial function?

A The factorial will be calculated correctly

B The program will crash with a stack overflow

C The function will return zero

D The function will return one

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

Which of these is the correct recursive formula for factorial(n)?

A factorial(n) = factorial(n-1) / n

B factorial(n) = n + factorial(n-1)

C factorial(n) = n * factorial(n-1)

D factorial(n) = factorial(n+1) * n

The factorial of n is n times factorial of (n-1).

Explain how the factorial function uses recursion to calculate factorial of a number.

Think about how the function reduces the problem step by step.

Describe why a base case is important in recursive functions like factorial.

Without it, the function would never stop calling itself.

Practice

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

easy

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

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

C. The number multiplied by 2

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 other operations.

3. Final Answer:

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

4. Quick Check:

   Factorial = product of integers [OK]

Hint: Factorial multiplies numbers down to 1 [OK]

Common Mistakes:

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

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

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 should return 1 when n is 0.

2. Step 2: Check options for correct base case

   Only if n == 0 { return 1 } returns 1 when n == 0, which is correct base case.

3. Final Answer:

   if n == 0 { return 1 } -> Option A

4. Quick Check:

   Base case n=0 returns 1 [OK]

Hint: Factorial base case returns 1 at zero [OK]

Common Mistakes:

• Returning 0 for base case
• Returning wrong value for n=1
• Missing base case causing infinite recursion

3. What is the output of this Go code?

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

fmt.Println(factorial(3))

medium

A. 3

B. 9

C. 6

D. 0

Solution

1. Step 1: Trace factorial(3) calls

   factorial(3) calls 3 * factorial(2), factorial(2) calls 2 * factorial(1), factorial(1) calls 1 * factorial(0), factorial(0) returns 1.

2. Step 2: Calculate return values

   factorial(1) = 1*1=1, factorial(2) = 2*1=2, factorial(3) = 3*2=6.

3. Final Answer:

   6 -> Option C

4. Quick Check:

   3! = 6 [OK]

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

Common Mistakes:

• Adding instead of multiplying
• Returning n instead of recursive call
• Missing base case causing stack overflow

4. Identify the error in this recursive factorial function:

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

medium

A. Missing base case for n == 0

B. Recursive call uses n instead of n-1 causing infinite recursion

C. Returns 0 instead of 1 in base case

D. Function should return float instead of int

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 n instead of n-1 causing infinite recursion -> Option B

4. Quick Check:

   Recursive call must reduce n [OK]

Hint: Recursive call must reduce input to reach base case [OK]

Common Mistakes:

• Calling factorial with same n causing infinite loop
• Wrong base case value
• Ignoring base case leading to stack overflow

5. How would you modify the recursive factorial function to handle negative inputs gracefully in Go?

hard

A. Use a loop instead of recursion for negative inputs

B. Remove base case and let recursion handle negative inputs

C. Return factorial of absolute value of n without check

D. Add a check to return 0 if n is negative before recursion

Solution

1. Step 1: Understand factorial domain

   Factorial is not defined for negative numbers, so function should handle negatives explicitly.

2. Step 2: Add input validation

   Adding a check to return 0 (or error) if n is negative prevents invalid recursion calls.

3. Final Answer:

   Add a check to return 0 if n is negative before recursion -> Option D

4. Quick Check:

   Validate input before recursion [OK]

Hint: Check for negatives before recursion to avoid errors [OK]

Common Mistakes:

• Ignoring negative inputs causing infinite recursion
• Using absolute value without validation
• Removing base case causing stack overflow