Recursion Base Case and Recursive Case in DSA Javascript - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is the base case in recursion?

The base case is the condition that stops the recursion. It prevents infinite calls by providing a simple answer without further recursion.

beginner

What is the recursive case in recursion?

The recursive case is the part where the function calls itself with a smaller or simpler input to solve the problem step by step.

intermediate

Why do we need both base case and recursive case in a recursive function?

The base case stops the recursion to avoid infinite loops, and the recursive case breaks the problem into smaller parts to solve it gradually.

beginner

Consider this code snippet:<br><pre>function factorial(n) {<br>  if (n === 0) return 1;<br>  return n * factorial(n - 1);<br>}</pre><br>Identify the base case and recursive case.

Base case: if (n === 0) return 1;
Recursive case: return n * factorial(n - 1);

beginner

What happens if a recursive function has no base case?

The function will keep calling itself forever, causing a stack overflow error because it never stops.

What is the purpose of the base case in recursion?

A To print the result

B To call the function again

C To make the problem bigger

D To stop the recursion

The base case stops the recursion to prevent infinite calls.

In the recursive case, the function usually calls itself with:

A A larger input

B A smaller or simpler input

C The same input

D No input

The recursive case calls the function with a smaller or simpler input to solve the problem step by step.

What will happen if a recursive function lacks a base case?

A It will cause an infinite loop and crash

B It will run faster

C It will return immediately

D It will print the input

Without a base case, recursion never stops, causing infinite calls and a crash.

In this code, what is the base case?

function sum(n) {
  if (n <= 0) return 0;
  return n + sum(n - 1);
}

A return n + sum(n - 1);

B n - 1

C if (n <= 0) return 0;

D function sum(n)

The base case is the condition that stops recursion: if (n <= 0) return 0;

Which part of recursion breaks the problem into smaller parts?

A Recursive case

B Base case

C Function declaration

D Return statement

The recursive case breaks the problem into smaller parts by calling the function itself.

Explain in your own words what the base case and recursive case are in recursion.

Think about how recursion stops and how it continues.

Describe what would happen if a recursive function does not have a base case.

Imagine a function calling itself forever without stopping.

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