Hofstadter's G Sequence Recurrence in Java

user_14879696 0
Viewed 26

I am building the Hofstadter's G sequence in Java using recurrence but it's not working as wanted.

The Hofstadter G sequence is defined as follows:

G(0)=0
G(n)= n-G(G(n-1)), n>0

The first few terms of this sequence are 0, 1, 1, 2, 3, 3, 4, 4, 5, 6, 6, 7, 8, 8, 9, 9, 10, 11, 11, 12, 12, ...

I've written the following method that is not currently working:

  public static int G(int n) { 
    int i=0;
    int result = 0;

    if(n==0) return 0;

    for (i = 1; i <= n; i++) {
       result= i - G(G(i - 1));
       System.out.println(result);
    }

    return result;
  }
recurrence sequence loops java
1 Answers

You can directly implement a recursive method based on the definition:

public static int G(int n){
    return n == 0 ? 0 : n - G(G(n - 1));
}

To optimize this, you can consider using memoization.

user_95131840
Related