Factorial Using Recursion in DSA Go - Build from Scratch

Factorial Using Recursion

📖 Scenario: Imagine you are a chef who needs to calculate the number of ways to arrange a set of dishes on a menu. This is called a factorial calculation, which means multiplying a number by all the numbers below it down to 1.

🎯 Goal: You will write a Go program that calculates the factorial of a number using a recursive function. Recursion means the function calls itself to solve smaller parts of the problem until it reaches the simplest case.

📋 What You'll Learn

Create a variable to hold the number to calculate the factorial for

Create a recursive function called factorial that takes an integer and returns an integer

Use a base case in the factorial function to stop recursion when the input is 1

Use recursion to calculate the factorial for numbers greater than 1

Print the factorial result

💡 Why This Matters

🌍 Real World

Factorials are used in counting problems, like arranging items or calculating probabilities.

💼 Career

Understanding recursion and factorials helps in algorithm design and problem solving in software development.

1

Create the number variable

Create an integer variable called number and set it to 5.

DSA Go

# Your code here

Hint

Use number := 5 inside the main function.

2

Write the recursive factorial function

Write a recursive function called factorial that takes an integer n and returns an integer. Use a base case that returns 1 when n == 1.

DSA Go

package main

import "fmt"

func main() {
    number := 5
}

// Write the factorial function below

Hint

Check if n == 1 and return 1. Otherwise, return n * factorial(n-1).

3

Call the factorial function

Inside the main function, create a variable called result and set it to the call factorial(number).

DSA Go

package main

import "fmt"

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

func main() {
    number := 5
    // Call factorial and store in result
}

Hint

Use result := factorial(number) inside main.

4

Print the factorial result

Use fmt.Println to print the value of result inside the main function.

DSA Go

package main

import "fmt"

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

func main() {
    number := 5
    result := factorial(number)
    // Print the result
}

Hint

Use fmt.Println(result) to display the factorial.

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