Recursion Base Case and Recursive Case in DSA Javascript

Mental Model

Recursion solves a problem by calling itself with smaller parts until it reaches a simple case it can answer directly.

Analogy: Imagine a set of nested boxes. To find a small item inside, you open the biggest box, then the next smaller box inside it, and so on until you find the smallest box with the item. The smallest box is the base case where you stop opening more boxes.

function recurse(n) {
  if (n === 0) return;
  recurse(n - 1);
}

Base case: n = 0 -> stop
Recursive case: n > 0 -> call recurse(n - 1)

Dry Run Walkthrough

Input: Calculate factorial of 3 using recursion

Goal: Find factorial(3) by breaking it down into smaller factorial calls until base case

Step 1: Call factorial(3), since 3 > 0, call factorial(2)

factorial(3) -> factorial(2) -> ?

Why: We reduce the problem size by calling factorial with smaller number

Step 2: Call factorial(2), since 2 > 0, call factorial(1)

factorial(3) -> factorial(2) -> factorial(1) -> ?

Why: Keep reducing until we reach base case

Step 3: Call factorial(1), since 1 > 0, call factorial(0)

factorial(3) -> factorial(2) -> factorial(1) -> factorial(0)

Why: Keep reducing until base case

Step 4: Call factorial(0), base case reached, return 1

factorial(0) returns 1

Why: Base case stops recursion and returns known value

Step 5: Return factorial(1) = 1 * factorial(0) = 1 * 1 = 1

factorial(1) returns 1

Why: Calculate factorial using recursive result

Step 6: Return factorial(2) = 2 * factorial(1) = 2 * 1 = 2

factorial(2) returns 2

Why: Calculate factorial using recursive result

Step 7: Return factorial(3) = 3 * factorial(2) = 3 * 2 = 6

factorial(3) returns 6

Why: Calculate factorial using recursive result

Result:

factorial(3) = 6

Annotated Code

DSA Javascript

function factorial(n) {
  if (n === 0) return 1; // base case: stop recursion
  return n * factorial(n - 1); // recursive case: reduce problem size
}

console.log(factorial(3));

if (n === 0) return 1;

check base case to stop recursion

return n * factorial(n - 1);

recursive call with smaller input to build solution

Output

6

Complexity Analysis

Time: O(n) because the function calls itself n times until it reaches the base case

Space: O(n) due to the call stack holding n recursive calls before unwinding

vs Alternative: Iterative approach uses O(1) space but recursion is simpler to write and understand for problems like factorial

Edge Cases

n = 0 (base case)

Returns 1 immediately without further calls

DSA Javascript

if (n === 0) return 1;

n = 1

Calls factorial(0) then returns 1 * 1 = 1

DSA Javascript

return n * factorial(n - 1);

negative n

No guard in code, leads to infinite recursion (stack overflow)

DSA Javascript

No explicit guard for negative input

When to Use This Pattern

When a problem can be broken into smaller versions of itself and has a clear stopping point, use recursion with base and recursive cases.

Common Mistakes

Mistake: Forgetting the base case causes infinite recursion and crash
Fix: Always include a base case that stops recursion

Mistake: Calling recursive case without reducing problem size leads to infinite loop
Fix: Make sure each recursive call moves closer to base case

Summary

Recursion solves problems by calling itself with smaller inputs until a simple base case is reached.

Use recursion when a problem naturally breaks down into smaller similar problems with a clear stopping condition.

The key is to have a base case to stop and a recursive case that reduces the problem size.

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