Hofstadters Q Sequence

Question

I have been staring at this for almost a week and do not know how to implement the java code. First, I wrote a recursive Hofstadters Q Sequence that computes the n(th) number in Hofstadter’s Q-sequence, for n ≥ 1 which is as follows Ps. the Hofstadters Q Sequence is sort of like the Fibonacci sequence, only that it is defined as follows:

Q(1) = 1, Q(2) = 1, and
Q(n) = Q(n − Q(n − 1)) + Q(n − Q(n − 2)), for n > 2

public static int Hofstadters(int n)
  {
    int result;

    if (n < 3)
      result = 1;
    else
      result = Hofstadters(n - (Hofstadters(n-1))) + Hofstadters(n - (Hofstadters(n-2)));
    return result;
  }

this works perfectly fine. Now I was challenged to write this code using a loop instead of recursion, and an array (to store numbers in the sequence as I compute them from Q(1) to Q(n)).

The idea is that I will put the Q(i) element into position i of the array, from 1 to n.

I do not even know how to start it. So far I have written just the code below and have been practically staring at my screen ever since:

public static void QSequence(int n)
  {
    int result;
    int [] arr;
    int value;

    arr = new int [n-1];
    arr[0] = 1;
    arr[1] = 1;

    for(int count = 2; count< arr.length; count++)
    {
      //code
    }
  }

Please any help and hints will be much appreciated, thanks

Answer 1

It should work:

package snippet;

public class Snippet {

    public static void main(String[] args) {
        System.out.println(QSequence(10));
    }

    public static int QSequence(int n) {
        int result;
        int[] arr;
        int value;

        arr = new int[n];
        arr[0] = 1;
        arr[1] = 1;

        for (int i = 2; i < arr.length; i++) {
            arr[i] = arr[i - arr[i - 1]] + arr[i - arr[i - 2]];
        }

        return arr[n - 1];
    }
}