Recursion Concept and Call Stack Visualization in DSA C++ - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to make the function call itself recursively.

DSA C++

void countdown(int n) {
    if (n == 0) {
        return;
    }
    std::cout << n << " ";
    countdown([1]);
}

Drag options to blanks, or click blank then click option'

An + 1

Bn - 1

Cn

D0

Attempts:

3 left

💡 Hint

Common Mistakes

Calling countdown with n + 1 causes infinite recursion.

Calling countdown with n does not reduce the problem size.

The function should call itself with n - 1 to count down towards zero.

2fill in blank

medium

Complete the code to calculate factorial of n recursively.

DSA C++

int factorial(int n) {
    if (n == 0) {
        return 1;
    }
    return n * factorial([1]);
}

Drag options to blanks, or click blank then click option'

An

Bn + 1

Cn - 1

D0

Attempts:

3 left

💡 Hint

Common Mistakes

Using n + 1 causes infinite recursion.

Returning n instead of recursive call result.

Factorial of n is n times factorial of n-1.

3fill in blank

hard

Fix the error in the recursive Fibonacci function call.

DSA C++

int fibonacci(int n) {
    if (n <= 1) {
        return n;
    }
    return fibonacci([1]) + fibonacci(n - 2);
}

Drag options to blanks, or click blank then click option'

An - 1

Bn + 1

Cn

D2

Attempts:

3 left

💡 Hint

Common Mistakes

Using n + 1 causes infinite recursion.

Using n instead of n-1 in first call.

Fibonacci calls fibonacci(n-1) and fibonacci(n-2) to sum previous two numbers.

4fill in blank

hard

Fill both blanks to create a recursive function that sums numbers from 1 to n.

DSA C++

int sumToN(int n) {
    if (n == 0) {
        return 0;
    }
    return n [1] sumToN([2]);
}

Drag options to blanks, or click blank then click option'

A+

Bn - 1

C*

Dn

Attempts:

3 left

💡 Hint

Common Mistakes

Using multiplication instead of addition.

Not reducing n in recursive call.

Sum from 1 to n is n plus sumToN(n-1).

5fill in blank

hard

Fill all three blanks to create a recursive function that reverses a string.

DSA C++

std::string reverseString(const std::string& s) {
    if (s.empty()) {
        return "";
    }
    return s.back() [1] reverseString(s.substr(0, [2]))[3];
}

Drag options to blanks, or click blank then click option'

A+

B-

Cs.size() - 1

Ds.size() + 1

Attempts:

3 left

💡 Hint

Common Mistakes

Using s.size() + 1 causes out of range error.

Using subtraction operator instead of concatenation.

The function appends last char plus reverse of substring excluding last char. The third blank is empty to complete the expression.

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)