Recursion Base Case and Recursive Case in DSA Javascript - 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

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 Javascript

function factorial(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 of 0.

Execution Table

Step	Operation	Input n	Base Case?	Action	Return Value	Call Stack Depth
1	Call factorial(3)	3	No	Call factorial(2)		1
2	Call factorial(2)	2	No	Call factorial(1)		2
3	Call factorial(1)	1	No	Call factorial(0)		3
4	Call factorial(0)	0	Yes	Return 1	1	4
5	Return from factorial(1)	1	No	Calculate 1 * 1	1	3
6	Return from factorial(2)	2	No	Calculate 2 * 1	2	2
7	Return from factorial(3)	3	No	Calculate 3 * 2	6	1
8	End			All calls returned	6	0

💡 Recursion ends when base case n === 0 is reached and returns 1.

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
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 function stop calling itself when n is 0?

Because at step 4 in the execution_table, the base case condition n === 0 is true, so the function returns 1 instead of calling itself again. This prevents infinite recursion.

How does the function combine results after recursive calls?

At steps 5 to 7, the function multiplies the current n by the return value of the smaller factorial call, combining results as it returns back up the call stack.

What happens to the call stack during recursion?

The call stack depth increases with each recursive call (steps 1 to 4) and decreases as each call returns (steps 5 to 8), shown in the variable_tracker.

Visual Quiz - 3 Questions

Look at the execution_table, what is the return value when factorial(1) returns?

A 1

B 0

C 2

D 3

💡 Hint

Check step 5 in the execution_table where factorial(1) returns.

At which step does the base case condition become true?

A Step 2

B Step 4

C Step 6

D Step 7

💡 Hint

Look for the step where 'Base Case?' column says 'Yes' in the execution_table.

If the base case was changed to n === 1, what would be the return value of factorial(1)?

A 1 * factorial(0)

B 0

C 1

D Undefined

💡 Hint

Consider how the base case affects the return value at n=1, referencing the base case check in the execution_table.

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 smaller call to finish, then combines result.
Without base case, recursion never ends.
Use base case to prevent infinite calls.

Full Transcript

This visualization shows how recursion works using factorial as an example. The function calls itself with smaller numbers until it reaches the base case where n equals zero. At that point, it returns 1. Then each previous call multiplies its n by the returned value, building up the final result. The call stack grows as calls go deeper and shrinks as they return. The base case is essential to stop infinite recursion. The execution table tracks each call, input, and return value step-by-step, while the variable tracker shows how n and call stack depth change. Key moments clarify why recursion stops and how results combine. The quiz tests understanding of these steps.

Practice

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

easy

A. To call the function again with a smaller input

B. To increase the input size for the next call

C. To stop the recursion and prevent infinite calls

D. To print the result of the recursion

Solution

1. Step 1: Understand what recursion does

   Recursion calls the same function repeatedly with smaller inputs.

2. Step 2: Identify the role of the base case

   The base case stops the recursion by providing a condition where no further calls happen.

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 infinite loops [OK]

Common Mistakes:

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

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

function factorial(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: Recall factorial base case

   Factorial of 0 is 1, so base case is when n equals 0.

2. Step 2: Match condition to code

   The condition n === 0 correctly stops recursion and returns 1.

3. Final Answer:

   n === 0 -> Option B

4. Quick Check:

   Base case for factorial = 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
• Using n === 1 misses factorial(0) base case

3. What will be the output of this recursive function call?

function sumTo(n) {
  if (n === 0) {
    return 0;
  }
  return n + sumTo(n - 1);
}
console.log(sumTo(3));

medium

A. 6

B. 3

C. 0

D. Error

Solution

1. Step 1: Trace recursive calls

   sumTo(3) calls 3 + sumTo(2), sumTo(2) calls 2 + sumTo(1), sumTo(1) calls 1 + sumTo(0), sumTo(0) returns 0.

2. Step 2: Calculate total sum

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

3. Final Answer:

   6 -> Option A

4. Quick Check:

   3+2+1+0 = 6 [OK]

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

Common Mistakes:

• Forgetting to add current n before recursive call
• Confusing base case return value
• Assuming output is just n instead of sum

4. Find the error in this recursive function to compute the nth Fibonacci number:

function fib(n) {
  if (n === 0) return 0;
  if (n === 1) return 1;
  return fib(n - 1) + fib(n - 2);
}
console.log(fib(-1));

medium

A. Missing base case for negative n causing infinite recursion

B. Incorrect base case values for fib(0) and fib(1)

C. Wrong recursive calls should be fib(n + 1) and fib(n + 2)

D. No error, output is correct

Solution

1. Step 1: Analyze base cases and input

   Base cases cover n=0 and n=1, but input is n=-1 which is not handled.

2. Step 2: Understand recursion with negative input

   Calling fib(-1) leads to fib(-2) and fib(-3) calls infinitely, no stop condition.

3. Final Answer:

   Missing base case for negative n causing infinite recursion -> Option A

4. Quick Check:

   Negative input needs base case [OK]

Hint: Check base cases cover all input ranges [OK]

Common Mistakes:

• Ignoring negative inputs in recursion
• Assuming fib(-1) is valid without base case
• Changing recursive calls incorrectly

5. You want to write a recursive function to reverse a string. Which base case and recursive case correctly achieve this?

function reverse(str) {
  if (___) {
    return ___;
  }
  return reverse(___) + str[0];
}

hard

A. str.length === 0 / str / str.slice(1)

B. str.length === 1 / str / str.slice(0, -1)

C. str === null / null / str.slice(1)

D. str === '' / str[0] / str.slice(1)

Solution

1. Step 1: Identify base case for empty string

   When string is empty (''), return the empty string to stop recursion.

2. Step 2: Define recursive call correctly

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

3. Final Answer:

   str === '' / str / str.slice(1) -> Option D

4. Quick Check:

   Empty string base case and slice(1) recursive call [OK]

Hint: Base case empty string, recursive call slice(1) [OK]

Common Mistakes:

• Using null instead of empty string as base case
• Returning wrong substring in recursive call
• Incorrect base case condition