Converting an Iterative Method to a Recursive one (Java)

The recurrence is defined a little oddly. I would rewrite it:

S₀ = 1
S_i = S_i-1 + i + 1  — ∀ i > 0

The routine can be simplified to not use an array:

public static int sequenceNonRecursive (int n) {
    int S_0 = 1;                      // 0th term is 1
    int S_i = S_0;                    // S_i starts at S_0
    for(int i = 1; i <= n; i++) {
        int S_i_minus_1 = S_i;        // use previous result to calculate next
        S_i = S_i_minus_1 + i + 1;    // next is previous added with index plus 1
    }
    return S_i;
}

Any loop can be converted into an equivalent recursive routine. The trick is that local variables turn into function parameters for the recursive routine and the loop control turns into an if. If the condition is false, the function returns with the result. Otherwise, the function does the computation as if it is the loop body, and then uses recursion to iterate.

As an illustration, given the function:

public static int someFunction (int n) {
    int result = DEFAULT_RESULT;
    for (int i = 0; i < n; ++i) {
        result = UPDATE_RESULT(i, n, result);
    }
    return result;
}

Then, the body of this function can be changed to call a recursive function instead:

public static int someFunction (int n) {
    return someFunctionWithRecursion(n, 0, DEFAULT_RESULT);
}

Notice how the initial values of local variables have been converted into parameters to the recursive routine. So, the recursive routine itself may look like:

public static int someFunctionWithRecursion (int n, int i, int result) {
    if (! (i < n)) {
        return result;
    }
    result = UPDATE_RESULT(i, n, result);
    return someFunctionWithRecursion(n, i+1, result);
}

Notice that in the recursive call, the result has been updated, and the control variable i has been incremented, just as an iteration would have done in the original for() loop version of the code.

As an aside: The recurrence you are working on actually has a closed form:

S_n = (½)(n+1)(n+2)

It's actually easier. Imagine that your method works for all n's and that unless n is zero (the base case) you use

sequenceRecursive(n-1)

to get the value of the previous number and just expect it to work. (and it will)

Under the hood it will recurse down to the base case and build up the value as the calls return.

Recursion is like breaking down the original problem into sub problems and trying to solve them. To start with you need to figure out the base case(which in your case is n=0). Now you can move ahead and see how you can handle cases where n > 0 by breaking it down to the base case. Creating the sequence for n then n-1 then n-2 and so on till you reach the base case is the key to solve this problem recursively.

Structure your code something like this (just giving hints, leaving you to figure out the rest of the problem):

public static int sequenceRecursive(int n){
    if( n == 0 )
        //return something....
    else
        //return something else, which recursively relies on previous values of sequenceRecursive()
}

Let's first add 1 to all n's in your second equation: (if we increase them, we need to decrease the range, seeing that it's correct should be trivial)

s[0] = 1
s[n] = s[n-1] + (n+1) for all n >= 1

Why do we want to do this?
In short, the function definition is sequence(int n), not sequence(int n-1).

Here s[i] just corresponds to calling your function with input parameter i.

And the basic idea for the code:

public static int sequence(int n){
    if (/* base case */)
        // return value for base case
    else
        // return other case, includes calling sequence(x) for some x
}

Hope that gives you enough to work from.

I got it, guys. Thank ALL of you for your help! I can't believe how stupidly simple this was. As soon as I figured it out, I gave myself a forceful facepalm. I'm pretty sure I understand recursion now.

public static int sequenceRecursive(int n){
       if( n == 0 )
            return 0;
        else
            return n + sequenceRecursive(n-1);
}