Factorial Using Recursion in DSA Go - Execution Trace

Concept Flow - Factorial Using Recursion

Call factorial(n)

↓

Check if n == 0 or 1?

Yes→Return 1

No↓

Call factorial(n-1)

↓

Multiply n * factorial(n-1)

↓

Return result

The function calls itself with n-1 until it reaches 0 or 1, then returns 1 and multiplies back up.

Execution Sample

DSA Go

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

Calculates factorial of n by calling itself with n-1 until base case.

Execution Table

Step	Call	n	Condition n<=1?	Return Value	Stack Depth
1	factorial(3)	3	No	-	1
2	factorial(2)	2	No	-	2
3	factorial(1)	1	Yes	1	3
4	Return from factorial(1)	-	-	1	3
5	Return from factorial(2)	-	-	2 * 1 = 2	2
6	Return from factorial(3)	-	-	3 * 2 = 6	1
7	End	-	-	-	0

💡 Recursion ends when n <= 1, returning 1 and unwinding the stack.

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	After Step 5	After Step 6	Final
n	-	3	2	1	2	3	-
Return Value	-	-	-	1	2	6	-
Stack Depth	0	1	2	3	2	1	0

Key Moments - 3 Insights

Why does the function call itself multiple times before returning a value?

Because factorial uses recursion, it keeps calling itself with smaller n until it reaches the base case (n <= 1). This is shown in steps 1 to 3 in the execution_table where calls stack up before returning.

What happens when n is 1 in the recursion?

At n=1 (step 3), the condition n <= 1 is true, so the function returns 1 immediately without further recursive calls. This stops the recursion from going deeper.

How does the multiplication happen during recursion?

After reaching the base case, the function returns values back up the call stack multiplying n by the returned factorial of n-1. This is shown in steps 5 and 6 where return values are calculated.

Visual Quiz - 3 Questions

Look at the execution_table, what is the return value when factorial(1) is called at step 3?

A factorial(0)

B 0

C 1

D Undefined

💡 Hint

Check the 'Return Value' column at step 3 in the execution_table.

At which step does the recursion start to return values back up the call stack?

A Step 3

B Step 1

C Step 5

D Step 7

💡 Hint

Look for the first step where 'Return Value' is not '-' in the execution_table.

If we call factorial(4) instead of factorial(3), how many total calls will be made before returning?

A 3

B 4

C 5

D 6

💡 Hint

Count calls from n down to 1, each call reduces n by 1 until base case.

Concept Snapshot

Factorial Using Recursion:
- Base case: if n <= 1, return 1
- Recursive case: return n * factorial(n-1)
- Calls stack until base case reached
- Then multiply results back up
- Simple and elegant for factorial calculation

Full Transcript

This visualization shows how factorial is calculated using recursion. The function calls itself with smaller values of n until it reaches the base case where n is 1 or less. At that point, it returns 1. Then the function returns multiply the current n by the returned value from factorial(n-1). This process continues until the original call returns the final factorial value. The execution table tracks each call, the condition check, return values, and stack depth to help understand the flow. Key moments clarify why recursion stacks calls and how multiplication happens during return. The quiz tests understanding of return values, recursion depth, and call counts.

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