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↓

Perform Recursive Call with Smaller Input

↓

Combine Result and Return

↓

End Function Call

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	Call Stack	Current n	Condition (n==0?)	Action	Return Value	Visual Call Stack
1	factorial(3)	3	False	Call factorial(2)		factorial(3)
2	factorial(3) -> factorial(2)	2	False	Call factorial(1)		factorial(3) factorial(2)
3	factorial(3) -> factorial(2) -> factorial(1)	1	False	Call factorial(0)		factorial(3) factorial(2) factorial(1)
4	factorial(3) -> factorial(2) -> factorial(1) -> factorial(0)	0	True	Return 1	1	factorial(3) factorial(2) factorial(1) factorial(0)
5	factorial(3) -> factorial(2) -> factorial(1)	1	False	Return 1 * 1 = 1	1	factorial(3) factorial(2) factorial(1)
6	factorial(3) -> factorial(2)	2	False	Return 2 * 1 = 2	2	factorial(3) factorial(2)
7	factorial(3)	3	False	Return 3 * 2 = 6	6	factorial(3)
8				All calls returned, final result = 6	6

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

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

Key Moments - 3 Insights

Why does the recursion stop at n == 0?

Because the base case condition (n == 0) returns a value without further recursive calls, stopping infinite recursion. See execution_table step 4.

What happens to the call stack when a recursive call returns?

The top call is removed from the stack and its return value is used by the previous call. This is shown in execution_table steps 5 to 7 where the stack shrinks.

Why do we multiply n with factorial(n-1) after the recursive call?

Because factorial(n) = n * factorial(n-1). The multiplication happens after the smaller problem returns, combining results as shown in steps 5, 6, and 7.

Visual Quiz - 3 Questions

Look at the execution_table at step 4, what is the return value when n == 0?

A 0

B 1

C n

D Undefined

💡 Hint

Check the 'Return Value' column at step 4 in execution_table.

At which step does the call stack start to shrink?

A Step 1

B Step 4

C Step 5

D Step 8

💡 Hint

Look at the 'Call Stack' and 'Visual Call Stack' columns to see when calls return.

If the base case was changed to n == 1, how would the return value at step 4 change?

A Return value would be 1 at n == 1

B Return value would be 0 at n == 0

C Return value would be n at n == 0

D No change

💡 Hint

Base case defines when recursion stops and what value is returned, see condition column.

Concept Snapshot

Recursion has two parts:
- Base Case: stops recursion (e.g., if n==0 return 1)
- Recursive Case: calls itself with smaller input (e.g., factorial(n-1))
Each call waits for smaller call to return, then combines result.
Without base case, recursion never ends.
Call stack grows with calls and shrinks on returns.

Full Transcript

Recursion works by calling the same function inside itself with smaller inputs. It must have a base case to stop calling itself, otherwise it loops forever. In the factorial example, when n is zero, the function returns 1 immediately. For other values, it calls factorial with n-1, waits for that result, then multiplies by n. The call stack grows as calls happen and shrinks as they return. This process is shown step-by-step in the execution table and variable tracker.

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 increase the input size for the next call

D. To stop the recursion and prevent infinite calls

Solution

1. Step 1: Understand recursion basics

   Recursion works by calling itself repeatedly until a stopping point is reached.

2. Step 2: Identify the role of base case

   The base case stops further recursive calls to avoid infinite loops.

3. Final Answer:

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

4. Quick Check:

   Base case = stop recursion [OK]

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

Common Mistakes:

• Confusing base case with recursive case
• Thinking base case calls recursion again
• Ignoring the need for a stopping condition

2. Which of the following is the correct syntax for a base case in this 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 == 1

D. n < 0

Solution

1. Step 1: Identify factorial base case

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

2. Step 2: Check options for correct base case

   n == 0 matches n == 0, which returns 1 stopping recursion correctly.

3. Final Answer:

   n == 0 -> Option B

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 < 0 which is invalid for factorial
• Confusing base case with recursive case

3. What will be the output of the following code?

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

int main() {
  std::cout << sum(3);
  return 0;
}

medium

A. 0

B. 3

C. 6

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 total sum

   sum(3) = 3 + 2 + 1 + 0 = 6.

3. Final Answer:

   6 -> Option C

4. Quick Check:

   Sum 1 to 3 = 6 [OK]

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

Common Mistakes:

• Returning n instead of n + sum(n-1)
• Missing base case causing infinite recursion
• Confusing output with just n

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. Recursive call increases n, causing infinite recursion

B. Function should return void, not int

C. Missing return statement in base case

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

Solution

1. Step 1: Analyze recursive call

   The function calls factorial(n + 1), which increases n each time, never reaching base case.

2. Step 2: Identify infinite recursion cause

   Because n grows, base case n == 1 is never met, causing infinite recursion.

3. Final Answer:

   Recursive call increases n, causing infinite recursion -> Option A

4. Quick Check:

   Recursive call must reduce n [OK]

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

Common Mistakes:

• Increasing n instead of decreasing in recursion
• Wrong base case value
• Ignoring infinite recursion risk

5. You want to write a recursive function to compute the nth Fibonacci number where fib(0) = 0 and fib(1) = 1. Which of the following correctly defines the base cases and recursive case?

hard

A. if (n == 0) return 0; if (n == 1) return 1; else return fib(n - 1) + fib(n - 2);

B. if (n == 1) return 0; if (n == 2) return 1; else return fib(n - 1) + fib(n - 2);

C. if (n <= 1) return n; else return fib(n + 1) + fib(n - 2);

D. if (n == 0) return 1; if (n == 1) return 1; else return fib(n - 1) + fib(n - 2);

Solution

1. Step 1: Identify correct base cases for Fibonacci

   By definition, fib(0) = 0 and fib(1) = 1 are base cases.

2. Step 2: Check recursive case correctness

   Recursive case sums fib(n-1) and fib(n-2), matching Fibonacci definition.

3. Final Answer:

   if (n == 0) return 0; if (n == 1) return 1; else return fib(n - 1) + fib(n - 2); -> Option A

4. Quick Check:

   Fibonacci base and recursive cases match definition [OK]

Hint: Base cases fib(0)=0, fib(1)=1; recursive sums previous two [OK]

Common Mistakes:

• Wrong base case values
• Increasing n in recursive calls
• Returning wrong values for base cases