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

Concept Flow - Recursion Concept and Call Stack Visualization

Call function with n

↓

Check base case: n == 0?

Yes→Return base value

No↓

Call function with n-1

↓

Wait for return from n-1 call

↓

Calculate result using returned value

↓

Return result

↓

Previous call resumes

↓

Final return to original caller

This flow shows how a recursive function calls itself with smaller inputs until it reaches a base case, then returns values 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 n 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)		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)		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)		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)	Return 1	Factorial(0) Factorial(1) Factorial(2) Factorial(3)
9	Return from Factorial(0)	0	Factorial(1) -> Factorial(2) -> Factorial(3)	1	Factorial(1) Factorial(2) Factorial(3)
10	Calculate 1 * 1	1	Factorial(1) -> Factorial(2) -> Factorial(3)		Factorial(1) Factorial(2) Factorial(3)
11	Return from Factorial(1)	1	Factorial(2) -> Factorial(3)	1	Factorial(2) Factorial(3)
12	Calculate 2 * 1	2	Factorial(2) -> Factorial(3)		Factorial(2) Factorial(3)
13	Return from Factorial(2)	2	Factorial(3)	2	Factorial(3)
14	Calculate 3 * 2	3	Factorial(3)		Factorial(3)
15	Return from Factorial(3)	3		6

💡 All recursive calls returned; final factorial(3) result is 6.

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	Final
n	3	3	2	1	0	0	1	2	3
Call Stack Size	0	1	2	3	4	3	2	1	0
Return Value					1	1	1	2	6

Key Moments - 3 Insights

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

Because the base case (n == 0) is not met yet, the function calls itself with n-1 to break the problem into smaller parts, as shown in steps 1-7 in the execution_table.

When does the function start returning values back up the call stack?

It starts returning when the base case is reached at step 8 (n == 0), returning 1, then each previous call calculates and returns its result, as seen in steps 9-15.

What does the call stack represent in recursion?

The call stack shows all active function calls waiting for their results. Each new call adds a layer (step 3,5,7), and returns remove layers (step 9,11,13,15).

Visual Quiz - 3 Questions

Look at the execution_table at step 7. How many active calls are on the call stack?

A 4

B 3

C 2

D 1

💡 Hint

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

At which step does the function first return a value?

A Step 10

B Step 9

C Step 8

D Step 7

💡 Hint

Look at the 'Return Value' column; step 8 shows 'Return 1' for n=0.

If the initial call was Factorial(4), how would the call stack size at step 7 change?

A Decrease to 3

B Increase to 5

C Stay at 4

D No calls on stack

💡 Hint

Each call adds one layer; starting at 4 means one more call than with 3.

Concept Snapshot

Recursion calls a function inside itself with smaller inputs.
It stops at a base case to avoid infinite calls.
Each call waits for the next to return a value.
The call stack grows with each call and shrinks on return.
Example: Factorial(n) = n * Factorial(n-1), base case n=0 returns 1.

Full Transcript

Recursion is when a function calls itself to solve smaller parts of a problem. It 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 and return a value. This waiting creates a call stack, where each call is stacked on top of the previous one. When the base case returns a value, each call uses that value to calculate its own result and returns it back down the stack. 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. This process shows how recursion and the call stack work together to solve problems step-by-step.

Practice

1. What happens when a recursive function calls itself without a stopping condition?

easy

A. It runs only once and stops

B. It immediately returns without doing anything

C. It causes an infinite loop leading to a stack overflow error

D. It converts into a normal loop automatically

Solution

1. Step 1: Understand recursion stopping condition

   A recursive function must have a base case to stop calling itself; otherwise, it keeps calling endlessly.

2. Step 2: Effect of missing base case

   Without a base case, the function calls stack up until memory runs out, causing a stack overflow error.

3. Final Answer:

   It causes an infinite loop leading to a stack overflow error -> Option C

4. Quick Check:

   Missing base case = infinite recursion [OK]

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

Common Mistakes:

• Assuming recursion stops automatically
• Confusing recursion with loops
• Thinking recursion runs only once without base case

2. Which of the following is the correct syntax to define a recursive method in C# that calculates factorial?

easy

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

B. int Factorial(int n) { while (n > 0) return n * Factorial(n - 1); return 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

   Factorial base case is when n == 0, return 1; this matches int Factorial(int n) { if (n == 0) return 1; else return n * Factorial(n - 1); } only.

2. Step 2: Check recursive call correctness

   Recursive call must reduce n by 1 and multiply; int Factorial(int n) { if (n == 0) return 1; else return n * Factorial(n - 1); } does this correctly.

3. Final Answer:

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

4. Quick Check:

   Base case n==0 and n*Factorial(n-1) [OK]

Hint: Base case returns 1; recursive call multiplies by n-1 factorial [OK]

Common Mistakes:

• Using wrong base case value
• Increasing n instead of decreasing
• Returning 0 instead of 1 in base case

3. What is the output of the following C# code?

static void PrintNumbers(int n) {
  if (n == 0) return;
  Console.Write(n + " ");
  PrintNumbers(n - 1);
}

PrintNumbers(3);

medium

A. 1 2 3

B. 0 1 2 3

C. 3 2 1 0

D. 3 2 1

Solution

1. Step 1: Trace the recursive calls

   PrintNumbers(3) prints 3, then calls PrintNumbers(2), prints 2, calls PrintNumbers(1), prints 1, then calls PrintNumbers(0) which returns.

2. Step 2: Collect printed output

   Printed numbers are 3, 2, 1 in that order, each followed by a space.

3. Final Answer:

   3 2 1 -> Option D

4. Quick Check:

   Print then recurse = descending order [OK]

Hint: Print before recursive call prints descending sequence [OK]

Common Mistakes:

• Assuming print happens after recursion
• Including 0 in output
• Confusing order of prints

4. The following recursive method is intended to print numbers from 1 to n. What is the error?

void PrintUp(int n) {
  if (n == 0) return;
  PrintUp(n - 1);
  Console.Write(n + " ");
}

PrintUp(-1);

medium

A. Infinite recursion because negative n never reaches 0

B. No error; it prints numbers correctly

C. Syntax error due to missing return type

D. Runtime error because Console.Write is invalid

Solution

1. Step 1: Analyze base case condition

   Base case stops recursion when n == 0, but if n starts negative, it never reaches 0.

2. Step 2: Effect of negative input

   Calling PrintUp(-1) causes infinite recursion because n keeps decreasing and never hits 0.

3. Final Answer:

   Infinite recursion because negative n never reaches 0 -> Option A

4. Quick Check:

   Base case unreachable with negative input [OK]

Hint: Check base case covers all input ranges [OK]

Common Mistakes:

• Assuming negative input is handled
• Thinking syntax or Console.Write causes error
• Ignoring infinite recursion possibility

5. Consider this recursive method that sums numbers from 1 to n:

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

What is the output of Sum(4) and how many times is the method called?

hard

A. Output: 10, Method calls: 4

B. Output: 10, Method calls: 5

C. Output: 15, Method calls: 5

D. Output: 15, Method calls: 4

Solution

1. Step 1: Calculate Sum(4) step-by-step

   Sum(4) = 4 + Sum(3), Sum(3) = 3 + Sum(2), Sum(2) = 2 + Sum(1), Sum(1) = 1 + Sum(0), Sum(0) = 0. So total = 4+3+2+1+0 = 10.

2. Step 2: Count method calls

   Calls happen for n=4,3,2,1,0 totaling 5 calls.

3. Final Answer:

   Output: 10, Method calls: 5 -> Option B

4. Quick Check:

   Sum 1 to 4 = 10; calls = n+1 [OK]

Hint: Sum calls = n+1; sum formula n(n+1)/2 for output [OK]

Common Mistakes:

• Counting calls as n instead of n+1
• Calculating sum incorrectly
• Ignoring base case call