Why Recursion Base Case and Recursive Case in DSA Javascript?

The Big Idea

What if you could solve big problems by solving tiny pieces again and again until done?

The Scenario

Imagine you want to find the total number of steps to climb a tall staircase by counting each step one by one manually.

You start at the bottom and try to count all steps without stopping until you reach the top.

The Problem

Counting each step manually is slow and tiring, especially if the staircase is very tall.

You might lose track or get confused about where you are, making mistakes easy.

The Solution

Recursion breaks the big problem into smaller, easier problems.

The base case tells when to stop counting (like reaching the top step).

The recursive case moves one step up and calls itself to count the rest.

Before vs After

✗ Before

function countSteps(steps) {
  let total = 0;
  for (let i = 1; i <= steps; i++) {
    total += 1;
  }
  return total;
}

✓ After

function countSteps(steps) {
  if (steps === 0) return 0;  // base case
  return 1 + countSteps(steps - 1);  // recursive case
}

What It Enables

It allows solving complex problems by repeating simple steps until a clear stopping point is reached.

Real Life Example

Calculating factorial of a number, where you multiply the number by factorial of one less, stopping at 1.

Key Takeaways

Base case stops the recursion to prevent infinite loops.

Recursive case breaks the problem into smaller parts.

Together, they make complex problems easier to solve step-by-step.

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