Recursion Base Case and Recursive Case in DSA Java - Execution Trace

Concept Flow - Recursion Base Case and Recursive Case

Start recursion

↓

Check base case?

↓

Return base

↓

Process returned value

↓

Return result

↓

End recursion

The recursion starts by checking if the base case is met. If yes, it returns a simple value. Otherwise, it calls itself with a smaller problem, processes the result, and returns it.

Execution Sample

DSA Java

int factorial(int n) {
  if (n == 0) return 1;  // base case
  return n * factorial(n - 1);  // recursive case
}

Calculates factorial of n using recursion with a base case when n is 0.

Execution Table

Step	Call	n	Base Case?	Action	Return Value	Call Stack Depth
1	factorial(3)	3	No	Call factorial(2)	-	1
2	factorial(2)	2	No	Call factorial(1)	-	2
3	factorial(1)	1	No	Call factorial(0)	-	3
4	factorial(0)	0	Yes	Return 1	1	4
5	factorial(1)	1	No	Return 1 * 1	1	3
6	factorial(2)	2	No	Return 2 * 1	2	2
7	factorial(3)	3	No	Return 3 * 2	6	1
8	-	-	-	Recursion ends	6	0

💡 Recursion ends when all calls return back to the original call with final result.

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	0	1	2	3	4	3	2	1	0

Key Moments - 3 Insights

Why does the recursion stop at n == 0?

Because at step 4 in the execution_table, the base case is met (n == 0), so the function returns 1 without making further recursive calls, preventing infinite recursion.

What happens to the call stack during recursion?

The call stack grows with each recursive call (steps 1 to 4) and shrinks as each call returns a value (steps 5 to 7), as shown in the Call Stack Depth column of the execution_table.

Why do we multiply n with factorial(n - 1) in the recursive case?

Because each recursive call returns the factorial of a smaller number, multiplying by n combines the current step's value with the result of the smaller problem, building up the final factorial.

Visual Quiz - 3 Questions

Look at the execution_table, what is the return value when factorial(1) finishes (Step 5)?

A 1

B 0

C 2

D 3

💡 Hint

Check the 'Return Value' column at Step 5 in the execution_table.

At which step does the base case occur in the execution_table?

A Step 5

B Step 3

C Step 4

D Step 6

💡 Hint

Look at the 'Base Case?' column to find where it says 'Yes'.

If the initial call was factorial(4), how many total calls would be on the call stack at the deepest point?

A 4

B 5

C 3

D 6

💡 Hint

The call stack depth increases by 1 with each recursive call until the base case.

Concept Snapshot

Recursion has two parts:
- Base case: stops recursion (e.g., n == 0)
- Recursive case: calls itself with smaller input (e.g., n * factorial(n-1))
Each call waits for the next to finish, then returns a value.
Call stack grows with calls and shrinks with returns.

Full Transcript

This visualization shows how recursion works with a base case and recursive case using factorial example. The recursion starts with factorial(3). It checks if n is 0 (base case). Since 3 is not 0, it calls factorial(2). This continues until factorial(0) is called, which returns 1. Then each call returns its result by multiplying n with the returned value from the smaller problem. The call stack depth grows as calls are made and shrinks as results return. The recursion ends when all calls return to the original call with the final factorial value.

Practice

1. In recursion, what is the purpose of the base case?

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 the base case role

   The base case is the condition where 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 ends recursion.

3. Final Answer:

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

4. Quick Check:

   Base case stops recursion [OK]

Hint: Base case stops recursion to avoid infinite 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 a recursive Java method that calculates factorial?

easy

A. if (n > 0) return n * factorial(n - 1);

B. return n * factorial(n + 1);

C. if (n == 0) return 1;

D. if (n == 1) factorial(n);

Solution

1. Step 1: Identify base case condition for factorial

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

2. Step 2: Check syntax correctness

   if (n == 0) return 1; correctly returns 1 when n == 0, stopping recursion.

3. Final Answer:

   if (n == 0) return 1; -> Option C

4. Quick Check:

   Base case for factorial is n == 0 [OK]

Hint: Base case returns fixed value, usually simplest input [OK]

Common Mistakes:

• Using wrong condition for base case
• Calling factorial with n + 1 causing infinite recursion
• Not returning a value in base case

3. What is the output of this Java code?

public class Test {
  public static int sum(int n) {
    if (n == 0) return 0;
    return n + sum(n - 1);
  }
  public static void main(String[] args) {
    System.out.println(sum(3));
  }
}

medium

A. StackOverflowError

B. 6

C. 0

D. 3

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 B

4. Quick Check:

   Sum 1+2+3 = 6 [OK]

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

Common Mistakes:

• Confusing base case return value
• Adding n - 1 instead of n
• Expecting output 3 instead of sum

4. Identify the error in this recursive Java method for factorial:

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

medium

A. Base case returns 0 instead of 1

B. Recursive call uses n + 1 instead of n - 1

C. Missing return statement in recursive case

D. No base case defined

Solution

1. Step 1: Check base case return value

   Factorial base case should return 1 for n == 0, but code returns 0.

2. Step 2: Understand impact of wrong base case

   Returning 0 causes factorial to always be 0 after recursion.

3. Final Answer:

   Base case returns 0 instead of 1 -> Option A

4. Quick Check:

   Factorial base case must return 1 [OK]

Hint: Base case for factorial returns 1, not 0 [OK]

Common Mistakes:

• Returning 0 in base case
• Using wrong recursive call direction
• Forgetting return keyword

5. Given this recursive method to compute Fibonacci numbers:

public static int fib(int n) {
  if (n <= 1) return n;
  return fib(n - 1) + fib(n - 2);
}

What is the output of fib(4) and explain why the base case is important here?

hard

A. 3; base case stops infinite recursion by returning n when n ≤ 1

B. 5; base case returns 0 always

C. 7; base case calls fib(0) and fib(1) repeatedly

D. StackOverflowError; no base case defined

Solution

1. Step 1: Calculate fib(4) using recursion

   fib(4) = fib(3) + fib(2); fib(3) = fib(2) + fib(1); fib(2) = fib(1) + fib(0); fib(1)=1, fib(0)=0.

2. Step 2: Compute values step-by-step

   fib(2)=1+0=1; fib(3)=1+1=2; fib(4)=2+1=3. Base case returns n when n ≤ 1, stopping recursion.

3. Final Answer:

   3; base case stops infinite recursion by returning n when n ≤ 1 -> Option A

4. Quick Check:

   fib(4) = 3 with base case stopping recursion [OK]

Hint: Base case returns n when n ≤ 1 to stop recursion [OK]

Common Mistakes:

• Miscomputing fib(4) as 5 or 7
• Ignoring base case importance
• Assuming base case returns 0 always