How to modify loop into recursion if we need to use index as a condition?

Question

Let's say we want to implement a sum algorithm I use C# as an illustration here:

// Iterative
int sum(int[] array) {
    int result = 0;
    foreach(int item in array) {
        result += item;
    }
    return item;
}

which is equivalent to

// Recursive
int sum(int[] array) {
    if(array.Length == 0) {
        return 0;
    }
    // suppose there is a SubArray function here
    return array[0] + sum(array.SubArray(1));
}

However, if we want to add a condition to the algorithm where we don't want to add the integer at index 2 to our result, we only need to add one conditional statement to our first (iterative) implementation.

Q: Is there any adaptation to our recursive one to make it work?

ggorlen · Accepted Answer · 2019-10-26 02:54:50Z

The recursive version is inefficient due to the repeated SubArray calls, making the time complexity O(n²). You can re-write this function to accept an additional index parameter, which also happens to be how you can implement skipping a particular index (or set of indices, if you choose).

In C#:

private static int SumSkipIndex(int[] arr, int skip, int i) 
{
    if (i >= arr.Length) return 0;

    return (i == skip ? 0 : arr[i]) + SumSkipIndex(arr, skip, i + 1);
}

If you don't like the added i parameter which changes the function header, just write a separate private recursive "helper" function that can be called from the wrapper with your preferred header.

I'm also assuming you don't wish to hardcode index 2 into the algorithm (if you do, remove the skip parameter and replace i == skip with i == 2).

using System;

class MainClass 
{
    private static int SumSkipIndex(int[] arr, int skip, int i) 
    {
        if (i >= arr.Length) return 0;

        return (i == skip ? 0 : arr[i]) + SumSkipIndex(arr, skip, i + 1);
    }

    public static int SumSkipIndex(int[] arr, int skip) 
    {
        return SumSkipIndex(arr, skip, 0);
    }

    public static void Main(string[] args) 
    {
        Console.WriteLine(SumSkipIndex(new int[]{16, 11, 23, 3}, 1)); // => 42
    }
}

Lastly, bear in mind that recursion is a terrible choice for this sort of algorithm (summing an array), even with the index version. We have to call a new function just to handle one number, meaning we have a lot of call overhead (allocating stack frames) and can easily blow the stack if the list is too long. But I'm assuming this is just a learning exercise.

Cheri · Accepted Answer · 2019-10-26 03:08:04Z

A consise solution can be done in C# 8 using array slices.

public static int SumArray(int[] arr, int exclude){
  if(arr.Length == 0){
    return 0;
  }
  return (exclude==0?0:arr[0]) + SumArray(arr[1..], exclude-1);
}

The ternary operator checks if the skip index is 0, and if it isn't it will decrement the skip index for the next recursive call. The array is reduced using the slice, which should be more performant than SubArray. (Someone fact check me on the latter)

EDIT: As the other answer has suggested, this causes a bloating of stack frames due to a lack of tail call recursion. The below solution would mitigate the issue by using tail call optimisation, adding the sum variable to the function instead. This means the recursive call can use the same stack frame rather than creating a new one to await the return value before completing the sum.

public static int SumArray(int[] arr, int exclude, int sum=0){
  if(arr.Length == 0){
    return sum;
  }
  return SumArray(arr[1..], exclude-1, sum + (exclude==0?0: arr[0]));
}

Collectives™ on Stack Overflow

How to modify loop into recursion if we need to use index as a condition?

2 Answers 2

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related