Factorial Using Recursion in DSA Go

Mental Model

A function calls itself with a smaller number until it reaches 1, then multiplies back up to get the factorial.

Analogy: Imagine stacking blocks: to find the total height, you stack one block and then ask how tall the rest of the stack is, repeating until only one block is left.

factorial(3)
  ↓ calls factorial(2)
    ↓ calls factorial(1)
      ↓ returns 1
    ← multiply 2 * 1 = 2
  ← multiply 3 * 2 = 6
result = 6

Dry Run Walkthrough

Input: Calculate factorial of 3

Goal: Find 3! = 3 * 2 * 1 = 6 using recursion

Step 1: Call factorial(3), which calls factorial(2)

factorial(3) -> factorial(2) ↑

Why: We reduce the problem by one to reach the base case

Step 2: Call factorial(2), which calls factorial(1)

factorial(3) -> factorial(2) -> factorial(1) ↑

Why: Keep reducing until base case 1 is reached

Step 3: factorial(1) returns 1 (base case)

factorial(3) -> factorial(2) ← 1

Why: Base case stops recursion and starts returning values

Step 4: factorial(2) returns 2 * 1 = 2

factorial(3) ← 2

Why: Multiply current number by result from smaller problem

Step 5: factorial(3) returns 3 * 2 = 6

result = 6

Why: Final multiplication gives factorial of 3

Result:

result = 6

Annotated Code

DSA Go

package main
import "fmt"

func factorial(n int) int {
    if n == 0 || n == 1 { // base case stops recursion
        return 1
    }
    return n * factorial(n-1) // multiply current n by factorial of n-1
}

func main() {
    result := factorial(3) // calculate factorial of 3
    fmt.Println(result) // print the result
}

if n == 0 || n == 1 { return 1 }

stop recursion when n reaches 0 or 1

return n * factorial(n-1)

recursive call multiplying current n by factorial of smaller number

Output

6

Complexity Analysis

Time: O(n) because the function calls itself n times until reaching 1

Space: O(n) due to the call stack growing with each recursive call

vs Alternative: Iterative approach uses O(1) space but recursion is simpler to write and understand

Edge Cases

n = 1 (minimum input)

Returns 1 immediately as base case

DSA Go

if n == 0 || n == 1 { return 1 }

n = 0 (now handled in code)

Returns 1 immediately as base case

DSA Go

if n == 0 || n == 1 { return 1 }

When to Use This Pattern

When you see a problem that can be broken into smaller identical problems, use recursion to solve it step by step.

Common Mistakes

Mistake: Missing base case causes infinite recursion
Fix: Add a condition to stop recursion when n reaches 1 or 0

Mistake: Not reducing the problem size (n-1) in recursive call
Fix: Call factorial(n-1) to move towards base case

Summary

Calculates factorial by calling itself with smaller numbers until 1.

Use recursion when a problem can be divided into smaller similar problems.

The key is the base case that stops recursion and the recursive call that reduces the problem size.

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