Welcome to the Treehouse Community

Want to collaborate on code errors? Have bugs you need feedback on? Looking for an extra set of eyes on your latest project? Get support with fellow developers, designers, and programmers of all backgrounds and skill levels here with the Treehouse Community! While you're at it, check out some resources Treehouse students have shared here.

Looking to learn something new?

Treehouse offers a seven day free trial for new students. Get access to thousands of hours of content and join thousands of Treehouse students and alumni in the community today.

Start your free trial

Computer Science

Recursion: Sum of Values in Array | Why is this not working?

I am writing a function to sum the values in a given array. Is there any reason the following code [in Java] would produce an erroneous result?

   public static int sum(int[] a, int left, int right) {
      if (left == right) {
         return 0;
      }   
       return sum(a, left, right - 1) + a[right - 1];
   }

1 Answer

Brendan Whiting
seal-mask
.a{fill-rule:evenodd;}techdegree seal-36
Brendan Whiting
Front End Web Development Techdegree Graduate 84,735 Points

Your base case is returning 0 if left == right. But if the left pointer and the right pointer are pointing to the same element, that means we have an inner list slice of size 1. And what we need to do is return the value of that element, not 0.

From there, it looks like your strategy is to split off the final element from the rest of the list, and gradually reduce it one by one. The only thing you need to change here is change a[right - 1] to a[right]. We need to add the value at the right pointer to the sum before we slice it off and then ignore it.

public static int sum(int[] a, int left, int right) {
    if (left == right) {
        return a[left];
    }
    return sum(a, left, right - 1) + a[right];
}

Here's an alternate solution where you might split the array by a midpoint and call sum on both sides.

public static int sum(int[] list, int left, int right) {
    if (left == right) {
        return list[left];
    }
    int midpoint = ((right - left) / 2) + left;
    return sum(list, left, midpoint) + sum(list, midpoint + 1, right);
}

In this case it doesn't really matter as far as efficiency. I think we'll end up with O(n) in either case. But there are other recursive algorithms where splitting it by a midpoint is going to be key so I just wanted to point out that option, like merge sort where we can O(log n) and slicing in half every time is how we get that logarithmic efficiency.

Thank you, this explanation is very helpful!!