java - Hofstadter 在 Java 中的 G 序列递归

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

标签： javaloopssequencerecurrence

Answer 1

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

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

为了优化这一点，您可以考虑使用 memoization。