java - 如何使这种递归方法成为迭代方法？

Question

我需要Raju()使用for循环来制作方法，所以我该怎么做？

public class Fall2012COP3337MidtermRecursion 
{
    // trace recursion
    public static void main(String[] args) 
    {        
        System.out.println("Raju(6) = " + Raju(6));        
    }

    // compute the nth Raju number
    private static long Raju(int n)
    {        
        if (n < 0)
           return 0L;
        if (n == 0 || n == 1)
           return 1L;

        return Raju(n-1) + Raju(n-2) + 1; // recurse
    }
}

Answer 1

这应该这样做......它会编译。来自 Lewyx 的以下帖子的更正版本。（循环条件和编译错误）

public class Fall2012COP3337MidtermRecursion {
    // trace recursion
    public static void main(String[] args) 
    {
        for (int i = 0; i < 20 ; i++){
            System.out.println("RajuRecursion("+i+") = " + RajuRecursion(i)); 
            System.out.println("RajuIterative("+i+") = " + RajuIterative(i));

            // we see same results :)
        }
    }

    // decent iterative variant
    private static long RajuIterative(int n){

        long sum=0;
        long l1 = 1;
        long l2 = 1;

        if(n<0) return 0L; 
        if(n<2) return 1L;

        while(0<--n)
        {
            sum=l1+l2+1;
            l2=l1;
            l1=sum;
        }
        return sum;
    }

    // compute the nth Raju number
    private static long RajuRecursion(int n)
    {        
        if (n < 0)
           return 0L;
        if (n == 0 || n == 1)
           return 1L;

        return RajuRecursion(n-1) + RajuRecursion(n-2) + 1; // recurse
    }
}

结果是：

RajuRecursion(0) = 1
RajuIterative(0) = 1
RajuRecursion(1) = 1
RajuIterative(1) = 1
RajuRecursion(2) = 3
RajuIterative(2) = 3
RajuRecursion(3) = 5
RajuIterative(3) = 5
RajuRecursion(4) = 9
RajuIterative(4) = 9
RajuRecursion(5) = 15
RajuIterative(5) = 15
RajuRecursion(6) = 25
RajuIterative(6) = 25
RajuRecursion(7) = 41
RajuIterative(7) = 41
RajuRecursion(8) = 67
RajuIterative(8) = 67
....

Answer 2

private static long Raju_Iterative(int n)
{        
    if (n < 0)
        return 0L;
    long a = 1L;
    long b = 1L;
    for(int i = 0; i < n-1; i++) {
        long c = a+b+1;
        a = b;
        b = c;
    }
    return b;
}

Answer 3

static long Raju(int n) {
    if (n < 0) return 0;
    if (n < 2) return 1;

    long nm1 = 1, nm2 = 1;
    for (int i = 2; i <= n; ++i) {
        long raju = nm1 + nm2 + 1;
        nm2 = nm1;
        nm1 = raju;
    }

    return raju;
}