Recursion Concept and Call Stack Visualization in DSA C++ - Execution Trace

Concept Flow - Recursion Concept and Call Stack Visualization

Function Called

↓

Check Base Case?

Yes→Return Base Value

No↓

Call Function Recursively

↓

Wait for Recursive Result

↓

Process Result

↓

Return Result

↓

Function Ends

Shows how a recursive function calls itself until a base case is met, then returns results back up the call stack.

Execution Sample

DSA C++

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

factorial(3);

Calculates factorial of 3 by calling itself with decreasing values until 0, then multiplies results back up.

Execution Table

Step	Operation	Current n	Call Stack (Top to Bottom)	Return Value	Visual Call Stack
1	Call factorial(3)	3	factorial(3)	-	factorial(3)
2	Check if n==0	3	factorial(3)	No	factorial(3)
3	Call factorial(2)	2	factorial(2) -> factorial(3)	-	factorial(2) ↑ factorial(3)
4	Check if n==0	2	factorial(2) -> factorial(3)	No	factorial(2) ↑ factorial(3)
5	Call factorial(1)	1	factorial(1) -> factorial(2) -> factorial(3)	-	factorial(1) ↑ factorial(2) ↑ factorial(3)
6	Check if n==0	1	factorial(1) -> factorial(2) -> factorial(3)	No	factorial(1) ↑ factorial(2) ↑ factorial(3)
7	Call factorial(0)	0	factorial(0) -> factorial(1) -> factorial(2) -> factorial(3)	-	factorial(0) ↑ factorial(1) ↑ factorial(2) ↑ factorial(3)
8	Check if n==0	0	factorial(0) -> factorial(1) -> factorial(2) -> factorial(3)	Yes	factorial(0) ↑ factorial(1) ↑ factorial(2) ↑ factorial(3)
9	Return 1 from factorial(0)	0	factorial(1) -> factorial(2) -> factorial(3)	1	factorial(1) ↑ factorial(2) ↑ factorial(3)
10	Calculate 1 * 1 and return from factorial(1)	1	factorial(2) -> factorial(3)	1	factorial(2) ↑ factorial(3)
11	Calculate 2 * 1 and return from factorial(2)	2	factorial(3)	2	factorial(3)
12	Calculate 3 * 2 and return from factorial(3)	3	-	6	-
13	End of recursion	-	-	-	-

💡 Recursion ends when base case n==0 is reached and returns 1, then results multiply back up.

Variable Tracker

Variable	Start	After Step 1	After Step 3	After Step 5	After Step 7	After Step 9	After Step 10	After Step 11	Final
n	-	3	2	1	0	0	1	2	3
Return Value	-	-	-	-	-	1	1	2	6
Call Stack Depth	0	1	2	3	4	3	2	1	0

Key Moments - 3 Insights

Why does the function keep calling itself without returning immediately?

Because each call waits for the result of the next recursive call before it can calculate and return its own result, as shown in steps 3, 5, and 7 where calls stack up.

What happens at the base case and why is it important?

At step 8, when n==0, the function returns 1 immediately without further calls. This stops infinite recursion and starts returning values back up the call stack.

How does the call stack visually represent the recursive calls?

The 'Visual Call Stack' column shows each active call stacked vertically, with the newest call on top, shrinking as returns happen (see steps 7 to 12).

Visual Quiz - 3 Questions

Look at the execution table at step 7, what is the current call stack?

A factorial(3) only

B factorial(0) -> factorial(1) -> factorial(2) -> factorial(3)

C factorial(1) -> factorial(2) -> factorial(3)

D Empty

💡 Hint

Check the 'Call Stack (Top to Bottom)' column at step 7.

At which step does the base case condition become true?

A Step 6

B Step 10

C Step 8

D Step 12

💡 Hint

Look for 'Check if n==0' with 'Yes' in the 'Return Value' column.

If factorial(4) was called instead of factorial(3), how would the call stack depth change at step 7?

A It would be 5 instead of 4

B It would remain 4

C It would be 3

D It would be 1

💡 Hint

Call stack depth increases by one for each additional recursive call before base case.

Concept Snapshot

Recursion calls a function within itself.
Each call waits for the next until base case.
Base case stops recursion and returns a value.
Call stack grows with each call and shrinks on return.
Visualize call stack as stacked function calls.
Useful for problems like factorial, Fibonacci, tree traversal.

Full Transcript

Recursion is a method where a function calls itself to solve smaller parts of a problem. The function keeps calling itself with smaller inputs until it reaches a base case, which stops the recursion. Each call waits for the next call to finish before it can return its result. This creates a call stack where each function call is stacked on top of the previous one. When the base case returns a value, the calls start returning one by one, combining results. For example, factorial(3) calls factorial(2), which calls factorial(1), which calls factorial(0). factorial(0) returns 1, then factorial(1) returns 1*1=1, factorial(2) returns 2*1=2, and factorial(3) returns 3*2=6. The call stack grows as calls are made and shrinks as results return.

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)