Hofstadter 的 G 序列在 Java 中重复出现

Question

我正在 Java 中使用递归构建 Hofstadter 的 G 序列，但它没有按预期工作。

Hofstadter G序列定义如下：

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

这个序列的前几项是 0, 1, 1, 2, 3, 3, 4, 4, 5, 6, 6, 7, 8, 8, 9, 9, 10, 11, 11 , 12, 12, ...

我编写了以下目前无法使用的方法：

  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;
  }

Answer 1

可以直接根据定义实现一个递归方法：

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

要对此进行优化，您可以考虑使用记忆。

Hofstadter 的 G 序列在 Java 中重复出现

Hofstadter's G Sequence Recurrence in Java

java

loops

sequence

recurrence