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 Again (Recursive Call)

↓

Wait for Recursive Result

↓

Process Result

↓

Return Result

↩Back to Caller or End

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);
}

int main() {
  printf("%d", factorial(3));
  return 0;
}

Calculates factorial of 3 using recursion, multiplying n by factorial of n-1 until base case 0.

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 (base case)	0	factorial(0) -> factorial(1) -> factorial(2) -> factorial(3)	1	factorial(0) returns 1 ↑ factorial(1) ↑ factorial(2) ↑ factorial(3)
10	Calculate 1 * 1	1	factorial(1) -> factorial(2) -> factorial(3)		factorial(1)
11	Return 1	1	factorial(1) -> factorial(2) -> factorial(3)	1	factorial(1) returns 1 ↑ factorial(2) ↑ factorial(3)
12	Calculate 2 * 1	2	factorial(2) -> factorial(3)		factorial(2)
13	Return 2	2	factorial(2) -> factorial(3)	2	factorial(2) returns 2 ↑ factorial(3)
14	Calculate 3 * 2	3	factorial(3)		factorial(3)
15	Return 6	3	factorial(3)	6	factorial(3) returns 6
16	Print result			6

💡 Recursion ends when base case n==0 is reached and returns 1; then results return back up the call stack.

Variable Tracker

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

Key Moments - 3 Insights

Why does the function keep calling itself instead of stopping immediately?

Because the base case (n == 0) is not met yet, so the function calls itself with n-1 as shown in steps 2, 4, 6, and 8 in the execution table.

How does the function know when to stop calling itself?

When n equals 0, the base case is true (step 8), so it returns 1 instead of calling itself again, stopping further recursion.

Why do we see multiple calls stacked before any return happens?

Each recursive call waits for the result of the next call before it can compute its own return value, creating a stack of calls as shown in the 'Call Stack' column until the base case returns.

Visual Quiz - 3 Questions

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

A factorial(3)

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

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

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

💡 Hint

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

At which step does the base case condition become true?

A Step 6

B Step 8

C Step 10

D Step 12

💡 Hint

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

If we change the initial call to factorial(4), 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 instead of 4

D It would be 1

💡 Hint

The call stack depth increases by one for each recursive call; check 'Call Stack Depth' in variable_tracker.

Concept Snapshot

Recursion calls a function inside itself until a base case stops it.
Each call waits for the next call's result, building a call stack.
Base case returns a value without recursion.
Results return back up the stack, combining to final answer.
Visualize recursion as stacking calls then unstacking returns.

Full Transcript

Recursion is when a function calls itself to solve smaller parts of a problem. It keeps calling itself until it reaches a base case, which stops the recursion. Each call waits for the next call to finish, creating a stack of calls known as the call stack. When the base case returns a value, each previous call uses that value to compute its own result and returns it back up. This process continues until the first call returns the final answer. The example code calculates factorial by multiplying n by factorial of n-1 until n is zero. The execution table shows each call, the current value of n, the call stack, and return values step by step. The variable tracker shows how n, return values, and call stack depth change over time. Key moments clarify why recursion continues until the base case and why calls stack up before returning. The visual quiz tests understanding of call stack state and base case timing. Recursion is like stacking plates: you keep stacking until you reach the bottom plate, then you unstack them one by one to get the final result.

Practice

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

easy

A. The function converts into a loop automatically.

B. It causes infinite recursion and eventually a stack overflow error.

C. The function runs only once and stops.

D. The function returns immediately without doing anything.

Solution

1. Step 1: Understand the role of base case in recursion

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

2. Step 2: Analyze what happens without a base case

   Without a base case, the function keeps calling itself endlessly, filling the call stack until it overflows.

3. Final Answer:

   It causes infinite recursion and eventually a stack overflow error. -> Option B

4. Quick Check:

   No base case = infinite recursion [OK]

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

Common Mistakes:

• Thinking recursion stops automatically without base case
• Confusing recursion with loops
• Assuming function returns without base case

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) { if (n == 1) return 0; else return n + factorial(n - 1); }

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

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

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

Solution

1. Step 1: Check base case correctness

   Factorial base case is when n == 0, return 1.

2. Step 2: Check recursive call and operation

   Recursive call should be factorial(n - 1) multiplied by n.

3. Final Answer:

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

4. Quick Check:

   Base case n==0 and multiply with factorial(n-1) [OK]

Hint: Base case returns 1; recursive call uses n-1 [OK]

Common Mistakes:

• Using while loop instead of recursion
• Wrong base case value or return
• 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);
  printf("%d ", n);
}

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

medium

A. 1 2 3

B. 3 2 1

C. 0 1 2 3

D. 3 2 1 0

Solution

1. Step 1: Trace recursive calls

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

2. Step 2: Print values after recursive calls return

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

3. Final Answer:

   1 2 3 -> Option A

4. Quick Check:

   Print after recursion = ascending order [OK]

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

Common Mistakes:

• Printing before recursive call (would reverse order)
• Including 0 in output incorrectly
• Confusing base case behavior

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

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

medium

A. The recursive call should be sum(n - 1) instead of sum(n).

B. The base case should return n instead of 0.

C. The function should use a loop instead of recursion.

D. The function should return n * sum(n - 1).

Solution

1. Step 1: Analyze recursive call argument

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

2. Step 2: Correct recursive call to reduce problem size

   It should call sum(n - 1) to move towards base case and stop recursion.

3. Final Answer:

   The recursive call should be sum(n - 1) instead of sum(n). -> Option A

4. Quick Check:

   Recursive call argument must decrease [OK]

Hint: Recursive call must reduce input to reach base case [OK]

Common Mistakes:

• Calling sum(n) again causing infinite recursion
• Changing base case incorrectly
• Using multiplication instead of addition

5. Consider this recursive function to reverse a string:

void reverse(char *str, int start, int end) {
  if (start >= end) return;
  char temp = str[start];
  str[start] = str[end];
  str[end] = temp;
  reverse(str, start + 1, end - 1);
}

int main() {
  char s[] = "hello";
  reverse(s, 0, 4);
  printf("%s", s);
  return 0;
}

What will be printed after running this program?

hard

A. helol

B. hello

C. olleh

D. error

Solution

1. Step 1: Understand the recursive swapping

   The function swaps characters at start and end indexes, then calls itself with start+1 and end-1.

2. Step 2: Trace swaps for "hello"

   Swaps 'h' and 'o' -> "oellh", then swaps 'e' and 'l' -> "olleh", then stops when start >= end.

3. Final Answer:

   olleh -> Option C

4. Quick Check:

   Recursive swaps reverse string [OK]

Hint: Swapping characters inward reverses string recursively [OK]

Common Mistakes:

• Not updating start and end indexes correctly
• Confusing base case condition
• Assuming string prints unchanged