java - Magical Number 的省时递归

Question

我正在解决神奇数字问题，其中第 n 个位置的数字是前 3 个数字的总和减 1。例如:0 1 1 1 2 3 5 9 16.... 等等。

我用两种方法解决了这个问题。

代码 1) 使用递归

int magicNumber(int n){
    int f = 0;
    if (n == 1)
        return 0;
    else if (n > 1 && n <= 4)
        return 1;
    else
        f = (magicNumber(n-1) + magicNumber(n-2) + magicNumber(n-3)) - 1;
    return f;
}

代码 2) 使用数组

void magicNumber(int n){
    long arr[] = new long[100];
    int i=1;
    for(i = 1; i <= n; i++)
    {
        if(i==1)
            arr[i] = 0;
        else if(i>1&&i<=4)
            arr[i] = 1;
        else
            arr[i] = (arr[i-1] + arr[i-2] + arr[i-3]) - 1;
    }
    System.out.println("Result is : "+arr[n]);
}

代码 1 当我向程序提供一个小整数时工作正常，但当输入更大的整数时它会挂起，而代码 2 运行良好没有任何问题。

所以我需要您的建议，如何提高递归程序代码1的性能？

Answer 1

您可以像这样加 express 归速度:

int magicNumber2(int n, int a, int b, int c){
  if (n <= 1) return a;
  return magicNumber2(n - 1, b, c, a + b + c - 1);
}

int magicNumber(int n) {
  magicNumber2(n, 0, 1, 1);
}