Recursion Concept and Call Stack Visualization in DSA C++ - Build from Scratch

Recursion Concept and Call Stack Visualization

📖 Scenario: Imagine you have a stack of plates. You want to count how many plates are in the stack, but you can only see the top plate. You decide to take one plate off at a time and count it, then put it back. This is like recursion, where a function calls itself to solve smaller parts of a problem.

🎯 Goal: You will build a simple recursive function in C++ that counts down from a given number to 1, printing each number. This will help you understand how recursion works and how the call stack grows and shrinks.

📋 What You'll Learn

Create a recursive function called countDown that takes an integer parameter n.

Use a base case to stop recursion when n is 0.

Print the current value of n before calling countDown recursively with n-1.

Call the countDown function from main with the starting number 5.

💡 Why This Matters

🌍 Real World

Recursion is used in many real-world problems like searching files in folders, solving puzzles, and processing tree structures.

💼 Career

Understanding recursion is essential for software developers to solve problems that involve repeated tasks or nested data.

1

Create the main function and starting number

Write a main function and create an integer variable called start with the value 5.

DSA C++

int main() {
    // Your code here
}

Hint

The main function is the starting point of a C++ program. Declare int start = 5; inside it.

2

Define the recursive function countDown

Define a function called countDown that takes an integer parameter n. Inside it, write a base case that returns if n is 0.

DSA C++

int main() {
    int start = 5;
    return 0;
}

// Define countDown function here
// Your code here

Hint

The base case stops recursion. Use if (n == 0) return; inside countDown.

3

Add recursive call and print statement

Inside countDown, print the value of n using std::cout. Then call countDown recursively with n - 1.

DSA C++

int main() {
    int start = 5;
    return 0;
}

void countDown(int n) {
    if (n == 0) {
        return;
    }
    // Print n and call countDown with n-1
    // Your code here
}

Hint

Use std::cout << n << std::endl; to print the number, then call countDown(n - 1); to continue counting down.

4

Call countDown from main and print output

In main, call the countDown function with the variable start. Then return 0.

DSA C++

#include 

int main() {
    int start = 5;
    // Call countDown with start
    // Your code here
    return 0;
}

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

Hint

Call countDown(start); inside main to start the countdown.

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)