Recursion on Arrays and Strings in DSA C# - Build from Scratch

Sum of Array Elements Using Recursion

📖 Scenario: Imagine you have a list of daily expenses and you want to find the total amount spent. Instead of adding them one by one using a loop, you will use a method that calls itself to find the total.

🎯 Goal: Build a recursive method to calculate the sum of all elements in an integer array.

📋 What You'll Learn

Create an integer array called expenses with the exact values: 100, 200, 300, 400, 500

Create an integer variable called length that stores the length of the expenses array

Write a recursive method called SumArray that takes the array and its length as parameters and returns the sum of the elements

Call the SumArray method with expenses and length and print the result

💡 Why This Matters

🌍 Real World

Recursion helps solve problems like summing expenses, searching, or processing data step-by-step, similar to peeling layers of an onion.

💼 Career

Understanding recursion is important for software developers to solve problems efficiently and write clean code for tasks like searching, sorting, and processing data.

1

Create the array of expenses

Create an integer array called expenses with these exact values: 100, 200, 300, 400, 500

DSA C#

# Create the integer array expenses with the values 100, 200, 300, 400, 500
// Your code here

Hint

Use int[] expenses = {100, 200, 300, 400, 500}; to create the array.

2

Store the length of the array

Create an integer variable called length that stores the length of the expenses array

DSA C#

int[] expenses = {100, 200, 300, 400, 500};
// Create an integer variable length to store the length of expenses
// Your code here

Hint

Use expenses.Length to get the array length.

3

Write the recursive method to sum the array

Write a recursive method called SumArray that takes an integer array arr and an integer n as parameters and returns the sum of the first n elements. Use the base case when n is 0 to return 0, otherwise return the last element plus the sum of the rest.

DSA C#

int[] expenses = {100, 200, 300, 400, 500};
int length = expenses.Length;

// Write the recursive method SumArray here
// Your code here

Hint

Check if n is 0 to stop recursion. Otherwise add the last element arr[n - 1] to the sum of the rest.

4

Call the recursive method and print the result

Call the SumArray method with expenses and length as arguments and print the returned sum using Console.WriteLine

DSA C#

int[] expenses = {100, 200, 300, 400, 500};
int length = expenses.Length;

int SumArray(int[] arr, int n)
{
    if (n == 0)
        return 0;
    return arr[n - 1] + SumArray(arr, n - 1);
}

// Call SumArray with expenses and length, then print the result
// Your code here

Hint

Call SumArray(expenses, length) and print the result with Console.WriteLine.

Practice

1. What is the main idea behind using recursion on arrays or strings?

easy

A. Sorting the array or string before processing

B. Using loops to iterate over each element

C. Breaking the problem into smaller similar problems until a base case is reached

D. Storing all elements in a new data structure

Solution

1. Step 1: Understand recursion concept

   Recursion solves problems by calling itself with smaller inputs until a simple base case is reached.

2. Step 2: Apply to arrays or strings

   For arrays or strings, recursion processes one element and then calls itself on the rest.

3. Final Answer:

   Breaking the problem into smaller similar problems until a base case is reached -> Option C

4. Quick Check:

   Recursion = divide and conquer [OK]

Hint: Think: solve small part, then repeat on smaller input [OK]

Common Mistakes:

• Confusing recursion with loops
• Ignoring the base case
• Trying to process all elements at once

2. Which of the following is the correct base case for a recursive function that processes a string character by character?

easy

A. if (str[0] == '\0') return;

B. if (str == null) return;

C. if (str.Length > 0) return;

D. if (str.Length == 0) return;

Solution

1. Step 1: Identify base case for string recursion

   The base case should stop recursion when the string is empty (length zero).

2. Step 2: Check options

   if (str.Length == 0) return; correctly checks if string length is zero to stop recursion.

3. Final Answer:

   if (str.Length == 0) return; -> Option D

4. Quick Check:

   Base case = empty string check [OK]

Hint: Base case usually checks for empty string or array length zero [OK]

Common Mistakes:

• Checking for null instead of empty string
• Using wrong condition like length > 0
• Checking for null character '\0' in C# strings

3. What will be the output of this C# recursive function call?

static int SumArray(int[] arr, int index) {
  if (index == arr.Length) return 0;
  return arr[index] + SumArray(arr, index + 1);
}

int[] nums = {1, 2, 3};
Console.WriteLine(SumArray(nums, 0));

medium

A. 6

B. 0

C. 3

D. StackOverflowException

Solution

1. Step 1: Trace recursive calls

   SumArray called with index 0 returns arr[0] + SumArray(1) = 1 + ... SumArray(1) returns 2 + SumArray(2) SumArray(2) returns 3 + SumArray(3) SumArray(3) returns 0 (base case)

2. Step 2: Calculate total sum

   Sum = 1 + 2 + 3 + 0 = 6

3. Final Answer:

   6 -> Option A

4. Quick Check:

   Sum of [1,2,3] = 6 [OK]

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

Common Mistakes:

• Forgetting base case leads to infinite recursion
• Returning wrong index or value
• Confusing index with length

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

static string Reverse(string s) {
  if (s.Length == 0) return s;
  return Reverse(s.Substring(1)) + s[0];
}

// Usage: Console.WriteLine(Reverse(null));

medium

A. It causes a NullReferenceException when input is null

B. It never reaches the base case

C. It returns the original string without reversing

D. It causes infinite recursion

Solution

1. Step 1: Analyze input null handling

   The function calls s.Length but if s is null, this causes NullReferenceException.

2. Step 2: Check base case and usage

   Base case is correct for empty string but does not handle null input, causing runtime error.

3. Final Answer:

   It causes a NullReferenceException when input is null -> Option A

4. Quick Check:

   Null input causes exception [OK]

Hint: Always check for null before accessing string properties [OK]

Common Mistakes:

• Not checking for null input
• Assuming empty string and null are same
• Ignoring exceptions from null dereference

5. Given a string, write a recursive function to check if it is a palindrome (reads same forward and backward). Which of these approaches is correct?

hard

A. Use recursion to sort the string and compare with original

B. Check if first and last characters are equal, then recurse on substring excluding them

C. Count characters recursively and check if count is even

D. Reverse the string using recursion and compare with original

Solution

1. Step 1: Understand palindrome check logic

   Palindrome means first and last characters match, and inner substring is also palindrome.

2. Step 2: Apply recursion

   Recursively check first and last chars, then call function on substring excluding them until base case (empty or single char).

3. Final Answer:

   Check if first and last characters are equal, then recurse on substring excluding them -> Option B

4. Quick Check:

   Palindrome check = compare ends + recurse [OK]

Hint: Compare ends, then recurse inside substring [OK]

Common Mistakes:

• Reversing string is less efficient
• Counting characters doesn't prove palindrome
• Sorting changes string order