Recursion Concept and Call Stack Visualization in DSA C++ - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Simple Recursive Function

What is the output of the following C++ code that uses recursion to print numbers?

DSA C++

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

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

A 3 2 1 0

B 3 2 1

C 0 1 2 3

D 1 2 3

💡 Hint

Think about when the print statement executes in relation to the recursive call.

The function calls itself decreasing n until it reaches 0, then prints numbers on the way back up the call stack.

So it prints 1, then 2, then 3.

❓ Predict Output

intermediate

Sum of Numbers Using Recursion

What is the value of variable result after running this C++ recursive function?

DSA C++

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

int main() {
    int result = sum(4);
    std::cout << result;
    return 0;
}

A 10

B 24

C 0

D 4

💡 Hint

Sum of first n natural numbers is n*(n+1)/2.

The function adds numbers from 4 down to 1 recursively: 4 + 3 + 2 + 1 = 10.

🔧 Debug

advanced

Identify the Error in Recursive Function

What error will this C++ recursive function cause when called with countdown(3)?

DSA C++

void countdown(int n) {
    std::cout << n << " ";
    countdown(n - 1);
}

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

A No output because function never called

B Compilation error due to missing return type

C Stack overflow error due to missing base case

D Prints 3 2 1 0 and stops

💡 Hint

Check if the function has a condition to stop calling itself.

The function lacks a base case to stop recursion, so it calls itself infinitely until the program crashes with a stack overflow.

❓ Predict Output

advanced

Output of Recursive Factorial Function

What is the output of this C++ program that calculates factorial recursively?

DSA C++

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

int main() {
    std::cout << factorial(5);
    return 0;
}

A 24

B 120

C 5

D 1

💡 Hint

Factorial of 5 is 5*4*3*2*1.

The function multiplies numbers from 5 down to 1 recursively, resulting in 120.

🧠 Conceptual

expert

Call Stack Depth in Recursive Calls

If a recursive function calls itself with n-1 until n == 0, what is the maximum depth of the call stack when called with n = 7?

A 8

B 6

C 7

D 1

💡 Hint

Count how many times the function is called including the base case.

The function calls itself 7 times decreasing n from 7 to 1, plus one more call when n == 0 (base case), so total depth is 8.

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)