Recursion Base Case and Recursive Case in DSA C# - Execution Trace

Concept Flow - Recursion Base Case and Recursive Case

Start Recursive Function

↓

Check Base Case?

Yes→Return Base Value

No↓

Call Function Recursively with Smaller Input

↓

Combine Recursive Result

↓

Return Result

The function checks if it reached the simplest case (base case). If yes, it returns a value. Otherwise, it calls itself with a smaller input and combines the result.

Execution Sample

DSA C#

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

Calculates factorial of n using recursion with base case n==0.

Execution Table

Step	Operation	Current n	Action	Call Stack	Return Value
1	Call Factorial(3)	3	Check if n==0 (No)	[Factorial(3)]
2	Call Factorial(2)	2	Check if n==0 (No)	[Factorial(3), Factorial(2)]
3	Call Factorial(1)	1	Check if n==0 (No)	[Factorial(3), Factorial(2), Factorial(1)]
4	Call Factorial(0)	0	Check if n==0 (Yes), return 1	[Factorial(3), Factorial(2), Factorial(1), Factorial(0)]	1
5	Return from Factorial(1)	1	Calculate 1 * 1 = 1	[Factorial(3), Factorial(2)]	1
6	Return from Factorial(2)	2	Calculate 2 * 1 = 2	[Factorial(3)]	2
7	Return from Factorial(3)	3	Calculate 3 * 2 = 6	[]	6
8	Final Return	3	Return 6 to caller	[]	6

💡 Reached base case when n == 0, then returned and combined results back up the call stack.

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	After Step 4	After Step 5	After Step 6	After Step 7	Final
n	3	3	2	1	0	1	2	3	3
Call Stack	[]	[Factorial(3)]	[Factorial(3), Factorial(2)]	[Factorial(3), Factorial(2), Factorial(1)]	[Factorial(3), Factorial(2), Factorial(1), Factorial(0)]	[Factorial(3), Factorial(2)]	[Factorial(3)]	[]	[]
Return Value					1	1	2	6	6

Key Moments - 3 Insights

Why does the recursion stop calling itself at n == 0?

Because at step 4 in the execution_table, the base case condition n == 0 is true, so the function returns 1 without further recursive calls.

What happens if the base case is missing?

Without the base case, the recursion would never stop calling itself, causing a stack overflow error. The execution_table shows the importance of the base case at step 4.

Why do we multiply n by the recursive call's result when returning?

At steps 5, 6, and 7, the function combines the current n with the returned value from the smaller problem to build the final factorial result.

Visual Quiz - 3 Questions

Look at the execution_table, what is the call stack at step 3?

A [Factorial(3), Factorial(2), Factorial(1)]

B [Factorial(3), Factorial(2)]

C [Factorial(3)]

D []

💡 Hint

Check the 'Call Stack' column at step 3 in the execution_table.

At which step does the base case return a value?

A Step 2

B Step 4

C Step 6

D Step 8

💡 Hint

Look for the step where n == 0 and the function returns 1 in the execution_table.

If the input n was 4 instead of 3, how many total calls would appear in the call stack at the deepest point?

A 3

B 4

C 5

D 6

💡 Hint

The call stack grows by one for each recursive call until reaching n == 0, so for n=4, count calls from 4 down to 0.

Concept Snapshot

Recursion has two parts:
- Base Case: stops recursion (e.g., n == 0)
- Recursive Case: calls itself with smaller input
Each call waits for the next to return, then combines results.
Without base case, recursion never ends.
Example: factorial(n) = n * factorial(n-1), factorial(0) = 1.

Full Transcript

This visualization shows how recursion works using factorial as an example. The function calls itself with smaller values of n until it reaches zero, the base case. At that point, it returns 1. Then each previous call multiplies n by the returned value, building the final result. The call stack grows as calls are made and shrinks as they return. The base case is essential to stop infinite calls. The execution table tracks each step, showing the current n, the call stack, and return values. This helps understand how recursion unfolds and resolves.

Practice

1. What is the purpose of the base case in a recursive function?

easy

A. To print the result of the recursion

B. To call the function again with a smaller input

C. To stop the recursion and prevent infinite calls

D. To increase the input size for the next call

Solution

1. Step 1: Understand the role of base case

   The base case is the condition where the recursion stops to avoid infinite calls.

2. Step 2: Differentiate base case from recursive case

   The recursive case calls the function again, but the base case returns a value without further calls.

3. Final Answer:

   To stop the recursion and prevent infinite calls -> Option C

4. Quick Check:

   Base case = stop recursion [OK]

Hint: Base case stops recursion to avoid endless loops [OK]

Common Mistakes:

• Confusing base case with recursive case
• Thinking base case calls function again
• Ignoring base case leads to infinite recursion

2. Which of the following is the correct syntax for a base case in this C# recursive function to calculate factorial?

int Factorial(int n) {
    if (___) return 1;
    return n * Factorial(n - 1);
}

easy

A. n == 0

B. n > 0

C. n < 0

D. n == 1

Solution

1. Step 1: Identify the base case for factorial

   Factorial of 0 is defined as 1, so base case is when n == 0.

2. Step 2: Check options for correct base case condition

   Only 'n == 0' correctly stops recursion and returns 1.

3. Final Answer:

   n == 0 -> Option A

4. Quick Check:

   Factorial base case = n == 0 [OK]

Hint: Factorial base case is n equals zero [OK]

Common Mistakes:

• Using n > 0 as base case causes infinite recursion
• Using n == 1 misses factorial(0) definition
• Using n < 0 causes wrong behavior

3. What will be the output of this C# code?

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

Console.WriteLine(Sum(3));

medium

A. 6

B. 3

C. 0

D. Error

Solution

1. Step 1: Trace recursive calls for Sum(3)

   Sum(3) = 3 + Sum(2), Sum(2) = 2 + Sum(1), Sum(1) = 1 + Sum(0), Sum(0) = 0.

2. Step 2: Calculate return values step-by-step

   Sum(0) = 0, Sum(1) = 1 + 0 = 1, Sum(2) = 2 + 1 = 3, Sum(3) = 3 + 3 = 6.

3. Final Answer:

   6 -> Option A

4. Quick Check:

   Sum 1+2+3 = 6 [OK]

Hint: Sum from n to 0 adds all numbers [OK]

Common Mistakes:

• Confusing base case return value
• Adding n instead of subtracting in recursive call
• Expecting output as input value

4. Identify the error in this recursive function to find factorial:

int Factorial(int n) {
    if (n == 1) return 1;
    else return n * Factorial(n + 1);
}

medium

A. Missing else block causes syntax error

B. Base case should be n == 0, not n == 1

C. Function should return void, not int

D. Recursive call should use n - 1, not n + 1

Solution

1. Step 1: Analyze recursive call parameter

   The function calls Factorial(n + 1), which increases n, causing infinite recursion.

2. Step 2: Correct recursive call for factorial

   Factorial should call Factorial(n - 1) to reduce n and reach base case.

3. Final Answer:

   Recursive call should use n - 1, not n + 1 -> Option D

4. Quick Check:

   Factorial recursion decreases n [OK]

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

Common Mistakes:

• Increasing n causes infinite recursion
• Confusing base case condition
• Thinking else block is mandatory

5. You want to write a recursive function in C# to reverse a string. Which base case and recursive case are correct?

string Reverse(string s) {
    if (___) return ___;
    return Reverse(___) + s[0];
}

hard

A. s.Length == 1; ""; s.Substring(1)

B. s.Length == 0; s; s.Substring(1)

C. s.Length == 1; s; s.Substring(0, s.Length - 1)

D. s == null; null; s.Substring(1)

Solution

1. Step 1: Identify base case for empty string

   When string length is 0, return the string itself (empty string).

2. Step 2: Understand recursive case for reversing

   Call Reverse on substring from index 1 to end, then add first character at the end.

3. Final Answer:

   s.Length == 0; s; s.Substring(1) -> Option B

4. Quick Check:

   Empty string base case, substring recursive call [OK]

Hint: Base case empty string; recursive call on substring from index 1 [OK]

Common Mistakes:

• Using s == null instead of empty string
• Wrong substring indices causing errors
• Returning s instead of empty string in base case