多次递归迭代

Question

我正在学习 Java 并且为了练习，我必须实现一个递归和迭代方法，return 以下为正整数。

L(0) = 1
L(1) = 1
L(n) = L(n - 1) + L(n - 2) + 1  if  n > 1

递归的方法没问题

public static int rec (int n) {
    if (n > 1) {
        return rec (n-1) + rec(n-2) + 1;
    }
    else {
        return 1;
    }
}

我可以将简单的递归转换为迭代，反之亦然，但我不知道如何解决这个问题。你有什么建议吗？

编辑：感谢斐波那契数列的提示。我现在明白了：

public static int iter (int n) {
    int f0 = 1;
    int f1 = 1;
    int fn = 0;

    if (n > 1) {
        for (int i = 1; i < n; i++) {
            fn = f0 + f1 + 1;
            f0 = f1;
            f1 = fn;
        }
    }
    else {
        return 1;
    }
    return fn;
}

Answer 1

尝试简单地使用两个变量。

    public static int rec1(int n) {

    int result=0;
    int previous1=0;
    int previous2=0;

    int i=0;
    while(i<=n)
    {
        if(i==0 || i==1)
        {
            result=1;
        }
        else
        {
            result= previous1 + previous2 + 1;
        }

        previous2=previous1;
        previous1=result;
        i++;
    }
    return result;
}

Answer 2

你为什么对小谎 +1？

0,1,1,2,3,5,8,11 如果我没记错的话，前面2个数字的总和假设n大于1。

不应该是这样的吗：

int fib(int n){
if (n == 0){
       return 0;
   } else if (n == 1) {
       return 1;
   } //base case
   else{
       return fib(n-2)+fib(n-1);
   }

如果代码不完美，我们深表歉意，但您应该明白了。

迭代方法的另一个答案很好用，这只是用代码突出显示 +1，不应该是公认的答案:)

Answer 3

这是我的版本

public static int modifiedFibonacci(int n)
{
   if(n > 1){
       int f1 = 0;
       int f2 = 0;
       int result = 0;
       for (int i = 2; i <= n; i++)
       {
          result = f1 + f2 + 2;
          f2 = f1;
          f1 = result;
       }
       return ++result;
   }
   return 1;
}

多次递归迭代

Multiple recursion to iteration

java

iteration

algorithm

recursion