Recursion Concept and Call Stack Visualization in DSA C++

Mental Model

Recursion is when a function calls itself to solve smaller parts of a problem until it reaches a simple case.

Analogy: Imagine a set of nested boxes where each box contains a smaller box inside. You open each box until you find the smallest one, then close them back in reverse order.

Function call stack:
main()
  ↓
func() -> func() -> func() -> ... -> base case
Each arrow shows a new function call waiting to finish.

Dry Run Walkthrough

Input: Calculate factorial of 3 using recursion (factorial(3))

Goal: Find factorial(3) by breaking it down into smaller factorial calls until factorial(1)

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

Stack: factorial(3) ↑ -> factorial(2) ↑

Why: We break the problem into smaller parts by calling factorial with n-1

Step 2: factorial(2) calls factorial(1)

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

Why: Keep breaking down until base case factorial(1)

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

Stack: factorial(3) -> factorial(2) ↑ (waiting for factorial(1) result)

Why: Base case reached, start returning values back up

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

Stack: factorial(3) ↑ (waiting for factorial(2) result)

Why: Use returned value to compute current factorial

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

Stack: empty (all calls returned)

Why: Final result computed and recursion ends

Result:

Stack empty
Result: 6

Annotated Code

DSA C++

#include <iostream>
using namespace std;

// Recursive function to calculate factorial
int factorial(int n) {
    if (n == 0 || n == 1) {
        return 1; // base case
    }
    return n * factorial(n - 1); // recursive call
}

int main() {
    int num = 3;
    cout << "Factorial of " << num << " is " << factorial(num) << "\n";
    return 0;
}

if (n == 0 || n == 1) { return 1; }

Check base case to stop recursion

return n * factorial(n - 1);

Recursive call reduces problem size by 1

Output

Factorial of 3 is 6

Complexity Analysis

Time: O(n) because the function calls itself n times until the base case

Space: O(n) due to the call stack holding n function calls at once

vs Alternative: Iterative factorial uses O(1) space but recursion is easier to understand for problems naturally defined by smaller subproblems

Edge Cases

Input n = 1 (base case)

Returns 1 immediately without further calls

DSA C++

if (n == 0 || n == 1) { return 1; }

Input n = 0 (base case)

Returns 1 immediately without further calls

DSA C++

if (n == 0 || n == 1) { return 1; }

When to Use This Pattern

When a problem can be broken into smaller identical problems, use recursion to solve by calling the same function with simpler inputs.

Common Mistakes

Mistake: Missing or incorrect base case causing infinite recursion
Fix: Always define a clear base case that stops recursion

Mistake: Not reducing the problem size in recursive call
Fix: Ensure each recursive call moves closer to the base case by changing input

Summary

Recursion solves problems by calling the same function with smaller inputs until a simple case is reached.

Use recursion when a problem naturally breaks down into smaller similar problems.

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

Practice

1. What happens when a recursive function calls itself without a base case?

easy

A. The function keeps calling itself indefinitely, causing a stack overflow

B. The function stops immediately without any output

C. The function returns zero by default

D. The function executes only once and then stops

Solution

1. Step 1: Understand recursion base case role

   The base case stops the recursion by providing a condition to end calls.

2. Step 2: Analyze missing base case effect

   Without a base case, the function calls itself endlessly, filling the call stack.

3. Final Answer:

   The function keeps calling itself indefinitely, causing a stack overflow -> Option A

4. Quick Check:

   No base case = infinite calls [OK]

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

Common Mistakes:

• Thinking recursion stops automatically
• Assuming default return value ends recursion
• Confusing base case with recursive step

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

easy

A. int factorial(int n) { while (n > 0) return n * factorial(n - 1); }

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

C. int factorial(int n) { if (n == 1) return 0; else return n + factorial(n - 1); }

D. int factorial(int n) { if (n == 0) return 0; else return n * factorial(n + 1); }

Solution

1. Step 1: Check base case correctness

   int factorial(int n) { if (n == 0) return 1; else return n * factorial(n - 1); } uses base case n == 0 returning 1, which is correct for factorial.

2. Step 2: Verify recursive call and operation

   int factorial(int n) { if (n == 0) return 1; else return n * factorial(n - 1); } multiplies n by factorial(n-1), matching factorial definition.

3. Final Answer:

   int factorial(int n) { if (n == 0) return 1; else return n * factorial(n - 1); } -> Option B

4. Quick Check:

   Correct base case and recursive step = int factorial(int n) { if (n == 0) return 1; else return n * factorial(n - 1); } [OK]

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

Common Mistakes:

• Using while loop instead of recursion
• Wrong base case value
• Incorrect recursive call argument

3. What is the output of the following C++ code?

void printNumbers(int n) {
  if (n == 0) return;
  printNumbers(n - 1);
  std::cout << n << " ";
}

int main() {
  printNumbers(3);
  return 0;
}

medium

A. 3 2 1

B. 3 2 1 0

C. 1 2 3

D. 1 2 3 0

Solution

1. Step 1: Trace recursive calls

   printNumbers(3) calls printNumbers(2), then printNumbers(1), then printNumbers(0) which returns immediately.

2. Step 2: Print values after returning from recursion

   After reaching base case, prints 1, then 2, then 3 in order.

3. Final Answer:

   1 2 3 -> Option C

4. Quick Check:

   Print after recursion = ascending order [OK]

Hint: Print after recursive call prints ascending order [OK]

Common Mistakes:

• Printing before recursive call (would reverse order)
• Including zero in output
• Confusing call stack order

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

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

medium

A. The base case is incorrect; it should be n == 0

B. The function should return n * sum(n - 1) instead of addition

C. The function lacks a return statement in the base case

D. The recursive call uses the same argument n, causing infinite recursion

Solution

1. Step 1: Check recursive call argument

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

2. Step 2: Identify fix for recursion

   The recursive call should be sum(n - 1) to reduce n and reach base case.

3. Final Answer:

   The recursive call uses the same argument n, causing infinite recursion -> Option D

4. Quick Check:

   Recursive call argument must decrease [OK]

Hint: Recursive calls must progress toward base case [OK]

Common Mistakes:

• Not decreasing argument in recursion
• Wrong base case value
• Confusing addition with multiplication

5. Consider this recursive function to compute the nth Fibonacci number:

int fib(int n) {
  if (n <= 1) return n;
  return fib(n - 1) + fib(n - 2);
}

What is the number of times fib(1) is called when fib(4) is executed?

hard

A. 3

B. 2

C. 5

D. 4

Solution

1. Step 1: Expand fib(4) calls

   fib(4) calls fib(3) and fib(2). fib(3) calls fib(2) and fib(1). fib(2) calls fib(1) and fib(0).

2. Step 2: Count fib(1) calls

   fib(1) is called once from fib(3), once from fib(2) inside fib(3), and once from fib(2) directly called by fib(4). Total 3 times.

3. Final Answer:

   3 -> Option A

4. Quick Check:

   Count base calls in recursion tree = 3 [OK]

Hint: Draw recursion tree to count base calls [OK]

Common Mistakes:

• Counting calls only once per function
• Ignoring repeated calls in recursion
• Confusing fib(1) with fib(0)