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

Recall & Review

beginner

What is recursion in the context of arrays and strings?

Recursion is a method where a function calls itself to solve smaller parts of a problem until it reaches a simple case that can be solved directly.

beginner

How does recursion help in reversing a string?

Recursion breaks the string into smaller parts, reverses the smaller part, and then combines the characters in reverse order until the whole string is reversed.

beginner

What is the base case in recursion on arrays?

The base case is the simplest part of the array, often when the array is empty or has one element, where the function stops calling itself.

intermediate

Explain how recursion can be used to find the sum of elements in an array.

Recursion sums the first element with the sum of the rest of the array by calling itself on the smaller array until it reaches the base case of an empty array.

beginner

What happens if a recursive function on arrays or strings does not have a proper base case?

Without a proper base case, the function will keep calling itself forever, causing a stack overflow error.

What is the base case when recursively reversing a string?

A When the string is empty or has one character

B When the string has two characters

C When the string length is even

D When the string length is odd

The base case for reversing a string recursively is when the string is empty or has one character because it is already reversed.

How does recursion process an array to find the sum of its elements?

A By multiplying all elements

B By adding the last element to the sum of the rest of the array

C By sorting the array first

D By adding the first element to the sum of the rest of the array

Recursion adds the first element to the sum of the remaining elements by calling itself on the smaller array.

What is the risk of missing a base case in recursion on arrays or strings?

A The function will run forever causing a stack overflow

B The function will return incorrect results

C The function will run faster

D The function will skip elements

Without a base case, recursion never stops and causes a stack overflow error.

Which of these is a correct recursive step for checking if a string is a palindrome?

A Reverse the string iteratively

B Compare first and second characters only

C Compare first and last characters, then recurse on the substring excluding them

D Sort the string characters

To check palindrome recursively, compare the first and last characters, then check the substring inside recursively.

What does the recursive function do when it reaches the base case?

A It restarts the recursion

B It stops calling itself and returns a result

C It throws an error

D It calls itself again

At the base case, recursion stops and returns a simple result to build the final answer.

Explain how recursion works on arrays with an example of summing elements.

Think about how you can add one element and then ask the same question for the rest.

Describe the steps to reverse a string using recursion.

Focus on how the function breaks the problem into smaller parts.

Practice

1. What does a recursive function do when processing an array or string?

easy

A. It loops through the array or string without calling itself.

B. It creates a new array or string without using recursion.

C. It calls itself with a smaller part of the array or string until a base case is reached.

D. It only processes the first element and stops.

Solution

1. Step 1: Understand recursion basics

   A recursive function calls itself with a smaller input to solve a problem step-by-step.

2. Step 2: Apply to arrays or strings

   For arrays or strings, recursion processes smaller parts until it reaches a base case (like empty array or string).

3. Final Answer:

   It calls itself with a smaller part of the array or string until a base case is reached. -> Option C

4. Quick Check:

   Recursion = smaller input calls [OK]

Hint: Recursion breaks problem into smaller parts [OK]

Common Mistakes:

• Thinking recursion processes entire array at once
• Confusing recursion with loops
• Ignoring the base case

2. Which of the following is the correct base case for a recursive function that reverses a string s?

easy

A. if s == s[::-1]: return s

B. if s == None: return s

C. if len(s) > 0: return s

D. if len(s) == 0: return s

Solution

1. Step 1: Identify base case for recursion

   The base case stops recursion. For strings, empty string means no more characters to reverse.

2. Step 2: Check options

   if len(s) == 0: return s checks if string length is zero and returns it, which is correct base case.

3. Final Answer:

   if len(s) == 0: return s -> Option D

4. Quick Check:

   Base case = empty string check [OK]

Hint: Base case usually checks for empty input [OK]

Common Mistakes:

• Using wrong condition for base case
• Checking reversed string equality as base case
• Returning input without base case

3. What is the output of this Python code?

def sum_array(arr):
    if len(arr) == 0:
        return 0
    return arr[0] + sum_array(arr[1:])

print(sum_array([1, 2, 3, 4]))

medium

A. 1234

B. 10

C. 24

D. Error

Solution

1. Step 1: Understand recursion on array sum

   Function adds first element to sum of rest of array recursively until empty array returns 0.

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

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

3. Final Answer:

   10 -> Option B

4. Quick Check:

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

Hint: Add first element + recursive sum of rest [OK]

Common Mistakes:

• Concatenating numbers instead of adding
• Forgetting base case returns 0
• Misunderstanding slicing arr[1:]

4. Find the error in this recursive function that checks if a string is a palindrome:

def is_palindrome(s):
    if len(s) <= 1:
        return True
    if s[0] != s[-1]:
        return False
    return is_palindrome(s[1:-1])

print(is_palindrome('racecar'))

medium

A. The slicing s[1:-1] is correct and no error exists

B. The function will cause infinite recursion

C. The base case should check for len(s) == 0 only

D. The comparison s[0] != s[-1] is incorrect

Solution

1. Step 1: Analyze base case and recursion

   Base case checks if string length is 1 or 0, which is correct for palindrome check.

2. Step 2: Check slicing and comparison

   Slicing s[1:-1] removes first and last characters correctly. Comparison s[0] != s[-1] correctly detects mismatch.

3. Final Answer:

   The slicing s[1:-1] is correct and no error exists -> Option A

4. Quick Check:

   Correct base case and slicing = no error [OK]

Hint: Check base case and slicing carefully [OK]

Common Mistakes:

• Thinking base case must be only empty string
• Assuming slicing causes infinite recursion
• Misreading character comparison

5. Given a list of strings, write a recursive function to return a new list containing only the strings that start with the letter 'a'. Which of these recursive approaches is correct?

hard

A. Check first string; if it starts with 'a', include it and recurse on rest; else recurse on rest without including it.

B. Loop through list and add strings starting with 'a' without recursion.

C. Return the original list without filtering.

D. Check last string only and ignore the rest.

Solution

1. Step 1: Understand recursive filtering

   Recursion should process one element and decide to include it or not, then recurse on the rest.

2. Step 2: Apply to strings starting with 'a'

   If first string starts with 'a', include it in result list plus recursive call on rest; else skip it and recurse on rest.

3. Final Answer:

   Check first string; if it starts with 'a', include it and recurse on rest; else recurse on rest without including it. -> Option A

4. Quick Check:

   Recursive filter = check first + recurse rest [OK]

Hint: Include first if matches, else skip, then recurse [OK]

Common Mistakes:

• Using loops instead of recursion
• Ignoring elements except last
• Returning unfiltered list