Recursion on Arrays and Strings in DSA Javascript - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is recursion in the context of arrays and strings?

Recursion is a way to solve problems by having a function call itself with smaller parts of the array or string until it reaches a simple case it can solve directly.

beginner

How do you identify the base case in a recursive function for arrays or strings?

The base case is the simplest situation where the function can return an answer without calling itself again, often when the array or string is empty or has one element.

beginner

Explain what happens during the 'recursive call' step.

During the recursive call, the function calls itself with a smaller part of the array or string, moving closer to the base case each time.

beginner

Why is it important to reduce the problem size in each recursive call?

Reducing the problem size ensures the recursion moves toward the base case and eventually stops, preventing infinite loops.

beginner

What is a common mistake when writing recursive functions on arrays or strings?

A common mistake is forgetting to define a proper base case or not reducing the problem size, which causes the function to call itself forever.

What should a recursive function on a string do first?

A Print the whole string

B Reverse the string immediately

C Check if the string is empty or has one character

D Call itself without any change

The function should first check the base case, which is usually when the string is empty or has one character.

In recursion on arrays, what does the function usually do after processing the first element?

A Calls itself with the rest of the array

B Returns the first element

C Sorts the array

D Prints the array

After handling the first element, the function calls itself with the remaining part of the array to continue processing.

What happens if a recursive function has no base case?

A It runs forever and causes an error

B It returns immediately

C It works faster

D It skips recursion

Without a base case, the function keeps calling itself endlessly, leading to a stack overflow error.

Which of these is a valid base case for recursion on an array?

A Array is sorted

B Array length is 10

C Array contains only numbers

D Array length is 0

The base case often checks if the array is empty (length 0) to stop recursion.

What is the main goal of recursion on strings or arrays?

A Sort the data

B Break the problem into smaller parts and solve each

C Loop through the data multiple times

D Print the data

Recursion breaks the problem into smaller pieces and solves each piece until the whole problem is solved.

Describe the steps to write a recursive function that reverses a string.

Think about how to reduce the string size and build the reversed string step by step.

Explain why recursion is useful for processing arrays and strings.

Consider how recursion handles parts of data one at a time.

Practice

1. What does a recursive function on an array typically do to process the array elements?

easy

A. It uses loops instead of calling itself.

B. It processes one element and calls itself on the rest of the array.

C. It processes all elements at once without calling itself.

D. It only processes the first and last elements.

Solution

1. Step 1: Understand recursion on arrays

   Recursive functions handle one element and then call themselves on the smaller part (rest of the array).

2. Step 2: Identify the typical recursive pattern

   This pattern reduces the problem size by one element each call until the array is empty.

3. Final Answer:

   It processes one element and calls itself on the rest of the array. -> Option B

4. Quick Check:

   Recursion = process one + recurse rest [OK]

Hint: Recursion breaks problem into smaller parts [OK]

Common Mistakes:

• Thinking recursion processes all elements at once
• Confusing recursion with loops
• Ignoring the base case

2. Which of the following is the correct syntax to define a recursive function in JavaScript that takes an array as input?

easy

A. function recurse(arr) { if(arr.length === 0) return; recurse(arr.slice(1)); }

B. function recurse(arr) { while(arr.length > 0) recurse(arr); }

C. function recurse(arr) { for(let i=0; i

D. function recurse(arr) { if(arr.length === 0) return; recurse(arr.pop()); }

Solution

1. Step 1: Check base case and recursive call

   function recurse(arr) { if(arr.length === 0) return; recurse(arr.slice(1)); } correctly checks if array is empty and calls itself with the rest of the array using slice(1).

2. Step 2: Identify incorrect syntax in other options

   The version using while(arr.length > 0) recurse(arr); causes infinite recursion because it passes the same array; the version using for loop calls recurse on individual elements; the version using arr.pop() passes a single element, not an array.

3. Final Answer:

   function recurse(arr) { if(arr.length === 0) return; recurse(arr.slice(1)); } -> Option A

4. Quick Check:

   Base case + recurse smaller array = correct syntax [OK]

Hint: Base case + smaller input slice needed [OK]

Common Mistakes:

• Missing base case causing infinite recursion
• Passing wrong argument type in recursive call
• Using loops inside recursion incorrectly

3. What will be the output of the following code?

function sumArray(arr) {
  if (arr.length === 0) return 0;
  return arr[0] + sumArray(arr.slice(1));
}
console.log(sumArray([1, 2, 3, 4]));

medium

A. 1234

B. Error

C. undefined

D. 10

Solution

1. Step 1: Understand the recursive sum logic

   The function adds the first element to the sum of the rest recursively until array is empty.

2. Step 2: Calculate sum step-by-step

   1 + sumArray([2,3,4]) = 1 + (2 + sumArray([3,4])) = 1 + 2 + 3 + 4 = 10

3. Final Answer:

   10 -> Option D

4. Quick Check:

   Sum of [1,2,3,4] = 10 [OK]

Hint: Sum = first element + sum of rest [OK]

Common Mistakes:

• Concatenating numbers as strings
• Forgetting base case returns 0
• Using arr.pop() which mutates array

4. Find the error in this recursive function that reverses a string:

function reverseStr(str) {
  if (str.length === 1) return str;
  return reverseStr(str.slice(1)) + str[0];
}
console.log(reverseStr('abc'));

medium

A. Base case should check for empty string, not length 1.

B. The recursive call should use str.slice(0, -1) instead of str.slice(1).

C. The function should return str[0] + reverseStr(str.slice(1)) instead.

D. No error, the function works correctly.

Solution

1. Step 1: Analyze base case condition

   Base case checks if string length is 1, but for empty string it should return empty string to avoid errors.

2. Step 2: Understand recursion on empty string

   If input is empty, function should return empty string to stop recursion safely.

3. Final Answer:

   Base case should check for empty string, not length 1. -> Option A

4. Quick Check:

   Base case empty string needed for safe recursion [OK]

Hint: Base case must handle empty string [OK]

Common Mistakes:

• Using wrong base case length
• Confusing slice indexes
• Assuming function works without base case

5. Given a nested array like [1, [2, [3, 4], 5], 6], which recursive approach correctly flattens it into [1, 2, 3, 4, 5, 6]?

hard

A. Return the original array as is without changes.

B. Use a loop to add elements without recursion.

C. Check if element is array, recursively flatten it, else add element to result.

D. Only flatten one level using slice and concat.

Solution

1. Step 1: Identify recursive flattening logic

   To flatten nested arrays, check each element: if array, recurse; else add to result.

2. Step 2: Understand why other options fail

   Loops alone can't flatten nested arrays fully; one-level flattening misses deeper nesting; returning original array does nothing.

3. Final Answer:

   Check if element is array, recursively flatten it, else add element to result. -> Option C

4. Quick Check:

   Recursive flatten = check array + recurse + add element [OK]

Hint: Recursively flatten nested arrays by checking element type [OK]

Common Mistakes:

• Flattening only one level
• Not checking if element is array
• Ignoring nested deeper arrays