CODEWITHSUNDEEP
javarecursion
Sparkas
Sparkas

Reputation: 175

Error with simple recursion in Java

I have this very simple recursion tried out in Java and I get an StackOverflow-Error everytime I run it. I do have a condition for the recursion to end, but it still won't work. 

public class Rec {
    public static int arraySumRecursive(int[] a) {
        return sumRec(a, a.length-1);
    }

    private static int sumRec(int[] a, int i) {
        if(i == 0) {
            return a[i];
        } else {
            return a[i] + sumRec(a, i--);
        }
    }

    public static void main(String[] args) {
        int[] test = {1, 7, 2, 5};
        System.out.println(arraySumRecursive(test));
    }
}

I just don't know what the problem is. When I go through the program with pen and paper it adds up, but it still won't work.

Thanks in advance!

EDIT:

Thanks to everyone helping me out. I changed i-- to --i. I didn't know there was a difference!

Upvotes: 1

Views: 82

Answers (4)

Naruto
Naruto

Reputation: 4329

return a[i] + sumRec(a, --i);

or return a[i] + sumRec(a, i-1);

Change i-- to --i,i.e., decrement first then call,otherwise i is not updated and it is always 3 thereby going into infinite loop causing stackoverflow exception

Upvotes: 1

Patrick
Patrick

Reputation: 736

I'm not sure if on Java is the same but in a lot of C based languages when you use variable-- it will send its value then after it will decrement its value, so you should use variable++ or else when you get to the line

return a[i] + sumRec(a, i--);

it will call sumRec with the same value of i and after that decrease the value of i resulting in an StackOverflow

you could try --i or i - 1

Upvotes: 2

David
David

Reputation: 218798

This:

i--

evaluates to the current value of i and decrements it afterward. So you're always sending the same value of i to the next recursive step. Since i never changes, the recursion is infinite.

Just send the subtracted value exactly as you did in the initial call from arraySumRecursive():

return a[i] + sumRec(a, i - 1);

(You could also use the decrement operator like this: --i However, it's entirely unnecessary to actually store the decremented value in i since you're returning on that same line and never using i afterward. All you need to do is subtract the value, you don't need to update i.)

Upvotes: 4

DaoWen
DaoWen

Reputation: 33019

Change i-- to i-1. The expression i-- actually returns i, and then decrements it after.

Alternatively, you could use the pre-decrement operator: --i. That way, it decrements i first, and then returns the value. However, you really don't need to mutate i here, so just using i-1 probably makes the most sense.

Since i-- returns the same value as i (and then decrements it afterward), this means your recursive call sumRec(a, i--) is equivalent to sumRec(a, i). That's why you're getting infinite recursion (resulting in a StackOverflowError).

Upvotes: 6

Related Questions