Why Factorial Using Recursion in DSA Go?

The Big Idea

Discover how a simple function can call itself to solve big problems easily!

The Scenario

Imagine you want to find the factorial of a number, like 5! (which means 5 x 4 x 3 x 2 x 1). Doing this by hand means multiplying all numbers one by one, which can get tiring and confusing for bigger numbers.

The Problem

Manually multiplying each number takes a lot of time and you might lose track or make mistakes, especially with bigger numbers like 10! or 20!. It's slow and error-prone to do it step-by-step without a clear method.

The Solution

Recursion solves this by breaking the problem into smaller parts. It says: to find factorial of n, multiply n by factorial of (n-1). This repeats until it reaches 1, making the code simple and elegant.

Before vs After

✗ Before

func factorial(n int) int {
    result := 1
    for i := 1; i <= n; i++ {
        result *= i
    }
    return result
}

✓ After

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

What It Enables

Recursion lets you solve complex problems by breaking them into smaller, easier steps, making your code cleaner and easier to understand.

Real Life Example

Calculating combinations in a card game where you need factorials to find how many ways to pick cards from a deck.

Key Takeaways

Manual multiplication is slow and error-prone for big numbers.

Recursion breaks the problem into smaller, repeatable steps.

Recursive factorial code is simpler and easier to read.

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