Recursion Concept and Call Stack Visualization in DSA Go - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is recursion in simple terms?

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 a base case in recursion?

A base case is the simplest situation in a recursive function where it stops calling itself and returns a result directly.

intermediate

How does the call stack help in recursion?

The call stack keeps track of all the function calls waiting to finish. Each recursive call adds a new layer, and when a base case is reached, the stack unwinds to return results.

beginner

What happens if a recursive function has no base case?

Without a base case, the function keeps calling itself forever, causing the program to crash with a stack overflow error.

intermediate

Explain the flow of a simple factorial function using recursion.

The factorial function calls itself with smaller numbers until it reaches 1 (base case). Then it multiplies all the returned values step by step to get the final answer.

What does a recursive function always need to stop calling itself?

A A loop

B A base case

C A global variable

D An error handler

A base case tells the recursive function when to stop calling itself.

What does the call stack do during recursion?

A Runs all calls in parallel

B Deletes previous calls immediately

C Stores each recursive call until base case is reached

D Prevents recursion from happening

The call stack stores each call so the program can return results in the right order.

What error occurs if recursion never reaches a base case?

A Stack overflow

B Syntax error

C Type error

D Memory leak

Without a base case, the call stack grows too large causing a stack overflow.

In the factorial example, what is the base case?

A When n equals 0

B When n is greater than 10

C When n is negative

D When n equals 1

The factorial function stops recursion when n equals 1.

Which of these is NOT true about recursion?

A It never needs a base case

B It always uses a call stack

C It can be replaced by loops

D It solves problems by breaking them down

Recursion always needs a base case to stop calling itself.

Describe how recursion works using the call stack and base case.

Think about how each call waits for the next one to finish.

Explain why a base case is important in a recursive function.

What happens if the function never stops calling itself?

Practice

1. What happens when a recursive function calls itself without a stopping condition?

easy

A. It converts into a normal loop automatically

B. It immediately returns without doing anything

C. It runs only once and stops

D. It causes an infinite loop and eventually a stack overflow error

Solution

1. Step 1: Understand recursion without base case

   Without a stopping condition, the function keeps calling itself endlessly.

2. Step 2: Effect on call stack

   Each call adds a new frame to the call stack, which grows until memory runs out causing stack overflow.

3. Final Answer:

   It causes an infinite loop and eventually a stack overflow error -> Option D

4. Quick Check:

   Missing base case = infinite recursion [OK]

Hint: Always check for a base case to stop recursion [OK]

Common Mistakes:

• Thinking recursion stops automatically
• Confusing recursion with loops
• Ignoring stack overflow possibility

2. Which of the following is the correct syntax to define a recursive function in Go that calculates factorial of n?

easy

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

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

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

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

Solution

1. Step 1: Check function signature and return type

   Factorial returns an int, so function must return int type.

2. Step 2: Verify base case and recursive call

   Base case is n == 0 returning 1; recursive call multiplies n by factorial(n-1).

3. Final Answer:

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

4. Quick Check:

   Correct base case and return type = func factorial(n int) int { if n == 0 { return 1 } return n * factorial(n-1) } [OK]

Hint: Base case returns 1 for factorial(0) [OK]

Common Mistakes:

• Missing return type in function signature
• Returning 0 instead of 1 in base case
• Not returning value from function

3. What is the output of the following Go code?

func printCount(n int) {
    if n == 0 {
        return
    }
    fmt.Print(n, " ")
    printCount(n-1)
}

func main() {
    printCount(3)
}

medium

A. 3 2 1

B. 1 2 3

C. 3 2 1 0

D. 0 1 2 3

Solution

1. Step 1: Trace recursive calls and prints

   printCount(3) prints 3, then calls printCount(2), which prints 2, then calls printCount(1), which prints 1, then calls printCount(0) which returns.

2. Step 2: Confirm output sequence

   Output is printed before recursive call, so order is 3 2 1 with spaces.

3. Final Answer:

   3 2 1 -> Option A

4. Quick Check:

   Print before recursion = descending order [OK]

Hint: Print before recursion prints descending order [OK]

Common Mistakes:

• Assuming print happens after recursion
• Including 0 in output
• Confusing order of prints

4. Identify the error in this recursive Go function that calculates sum of numbers from 1 to n:

func sum(n int) int {
    if n == 1 {
        return 1
    }
    return n + sum(n)
}

medium

A. Function does not return any value

B. Missing base case for n == 0

C. Recursive call uses sum(n) instead of sum(n-1), causing infinite recursion

D. Base case returns wrong value

Solution

1. Step 1: Analyze recursive call parameter

   The function calls sum(n) again without decreasing n, causing infinite recursion.

2. Step 2: Correct recursive call

   It should call sum(n-1) to reduce n and reach base case.

3. Final Answer:

   Recursive call uses sum(n) instead of sum(n-1), causing infinite recursion -> Option C

4. Quick Check:

   Recursive call must reduce n [OK]

Hint: Recursive call parameter must change to approach base case [OK]

Common Mistakes:

• Calling sum(n) again without decrement
• Wrong base case value
• Not returning result from recursion

5. Given the recursive function below, what will be the output when calling mystery(4)? Explain the call stack behavior.

func mystery(n int) int {
    if n <= 1 {
        return n
    }
    return mystery(n-1) + mystery(n-2)
}

func main() {
    fmt.Println(mystery(4))
}

hard

A. 5

B. 3

C. 7

D. 6

Solution

1. Step 1: Recognize the function as Fibonacci calculation

   The function returns n if n <= 1, else sum of mystery(n-1) and mystery(n-2), matching Fibonacci logic.

2. Step 2: Calculate mystery(4) step-by-step

   mystery(4) = mystery(3) + mystery(2) mystery(3) = mystery(2) + mystery(1) = (mystery(1)+mystery(0)) + 1 = (1+0)+1=2 mystery(2) = mystery(1) + mystery(0) = 1 + 0 = 1 Sum: 2 + 1 = 3 Wait, re-check carefully: mystery(0)=0, mystery(1)=1 mystery(2)=1+0=1 mystery(3)=1+1=2 mystery(4)=2+1=3 But options show 3 and 5, so re-check Fibonacci sequence: 0,1,1,2,3,5... Actually mystery(4) = 3

3. Final Answer:

   3 -> Option B

4. Quick Check:

   Fibonacci(4) = 3 [OK]

Hint: Recognize Fibonacci pattern in recursion [OK]

Common Mistakes:

• Miscounting Fibonacci numbers
• Confusing base cases
• Ignoring call stack repeated calls