Recursion on Arrays and Strings in DSA Python - Build from Scratch

Sum of Array Elements Using Recursion

📖 Scenario: Imagine you have a list of daily expenses, and you want to find out the total amount spent. Instead of adding them one by one using a loop, you will use a simple method called recursion to add them up.

🎯 Goal: Build a small program that uses recursion to calculate the sum of all numbers in a list.

📋 What You'll Learn

Create a list called expenses with exact values: [100, 200, 300, 400, 500]

Create a variable called n that stores the length of expenses

Write a recursive function called sum_expenses that takes arr and index as parameters and returns the sum of elements up to index

Print the total sum returned by sum_expenses(expenses, n - 1)

💡 Why This Matters

🌍 Real World

Recursion helps solve problems where a task can be broken down into smaller similar tasks, like calculating totals, searching, or sorting.

💼 Career

Understanding recursion is important for software development roles that involve algorithms, data processing, and problem-solving.

1

Create the list of expenses

Create a list called expenses with these exact values: [100, 200, 300, 400, 500]

DSA Python

# Create the list called expenses with the given values
# Your code here

Hint

Use square brackets [] to create a list and separate numbers with commas.

2

Store the length of the list

Create a variable called n that stores the length of the list expenses using the len() function

DSA Python

expenses = [100, 200, 300, 400, 500]
# Create a variable n to store the length of expenses
# Your code here

Hint

Use len(expenses) to get the number of items in the list.

3

Write the recursive function to sum expenses

Write a recursive function called sum_expenses that takes parameters arr and index. It should return 0 if index is less than 0. Otherwise, return the element at arr[index] plus the result of calling sum_expenses(arr, index - 1)

DSA Python

expenses = [100, 200, 300, 400, 500]
n = len(expenses)

# Define the recursive function sum_expenses
# Your code here

Hint

Base case: when index is less than 0, return 0.
Recursive case: add current element to sum of previous elements.

4

Print the total sum of expenses

Print the total sum by calling sum_expenses(expenses, n - 1)

DSA Python

expenses = [100, 200, 300, 400, 500]
n = len(expenses)

def sum_expenses(arr, index):
    if index < 0:
        return 0
    return arr[index] + sum_expenses(arr, index - 1)

# Print the total sum of expenses
# Your code here

Hint

Use print() to show the result of the recursive function call.

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