Recursion Base Case and Recursive Case in DSA Javascript - Build from Scratch

Recursion Base Case and Recursive Case

📖 Scenario: Imagine you have a stack of boxes, and you want to count how many boxes are in the stack by taking one box off at a time until none are left.

🎯 Goal: You will write a recursive function in JavaScript that counts down from a number to zero using recursion. This will teach you how to set a base case and a recursive case in a function.

📋 What You'll Learn

Create a function called countDown that takes one parameter n

Use a base case to stop recursion when n is zero

Use a recursive case to call countDown with n - 1

Print the current value of n in each call

Call the function with the number 5

💡 Why This Matters

🌍 Real World

Recursion is used in many places like searching files in folders, solving puzzles, and processing nested data.

💼 Career

Understanding recursion helps in coding interviews and solving problems that involve repetitive tasks or nested structures.

1

Create the function skeleton

Create a function called countDown that takes one parameter n.

DSA Javascript

function countDown(n) {
  // Your code here
}

Hint

Start by writing the function header with the name countDown and one parameter n.

2

Add the base case

Inside the countDown function, add a base case that stops the recursion when n is equal to 0. Use an if statement to check if n === 0 and return from the function.

DSA Javascript

function countDown(n) {
  if (n === 0) {
    // Your code here
  }
}

Hint

The base case stops the function from calling itself when n reaches zero.

3

Add the recursive case

Inside the countDown function, after the base case, add a console.log(n) statement to print the current value of n. Then call countDown recursively with n - 1.

DSA Javascript

function countDown(n) {
  if (n === 0) {
    return;
  }
  // Your code here
}

Hint

The recursive case prints n and then calls countDown with one less than n.

4

Call the function and see the output

Call the countDown function with the argument 5 and print the output.

DSA Javascript

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

// Your code here

Hint

Call countDown(5) to start counting down from 5 to 1.

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