将递归方法变成迭代方法

Question

我必须创建两个方法来做同样的事情。这些方法必须计算从 0 到 30 的数字的 L(n)，其中 L(n) 定义为

L(0) = 1

L(1) = 1

L(n) = L(n - 1) + L(n - 2) + 1; when n > 1

第一个方法必须使用我成功完成的递归编写，第二个方法必须使用迭代（数组和 for 循环）第一种方法）

public static int rec(int x) {
  if (x == 0) return 1;
  if (x == 1) return 1;
  else return rec(x - 1) + rec(x - 2) + 1;
}

我在 main 中为第一种方法添加了这个

int x = 0;
    while (x <= 30) {
        System.out.println(rec(x));
        x++;
    }

这就是我用第二种方法所能做的全部，虽然我知道这是错误的，但请记住我是初学者，请保持温和第二种方法）

 public static long iter(long [] x){
    long result = 0  ;
    int length = x.length;
    for ( int i = 0 ; i < length ; i++){
        if ( i == 0 ) result = 1;
        if ( i == 1 ) result = 1;
        else  result += x[i-1]+x[i-2]+1;
    }
    return result ;
}

Answer 1

想想你的代码在做什么 -

for ( int i = 0 ; i < x.length ; i++){
           long returnvalue = x[i-1]+x[i-2]+1; // every iteration you are resetting returnvalue. 
    }

在每次迭代中，您都在创建一个新变量，然后丢失您刚刚计算的内容。您需要从每次迭代中添加此结果，因此您必须这样做 -

 for ( int i = 0 ; i < x.length ; i++){
           returnvalue = returnvalue + x[i-1]+x[i-2]+1;
    }

或者您也可以这样做 -

returnvalue +=  x[i-1]+x[i-2]+1;

请注意，在迭代版本中，returnValue 仅在循环开始前定义一次。

Answer 2

如何将 L 视为一个数组，然后执行以下赋值：

L(0) = 1

L(1) = 1

对于第 3 步，您将必须编写一个循环来计算和存储 L[2] 到 L[30] 的值。在循环的每次迭代中，前两个值已经在 L 中，因此您可以直接使用它们。

Answer 3

您非常接近 - 您需要在您的 iterating 解决方案中保留历史记录：

public static long iter(long x) {
    long result = 0;
    // Make a 2-length array for my history.
    long[] history = new long[2];
    for (int i = 0; i <= x; i++) {
        if (i < 2) {
            result = 1;
        } else {
            result = history[0] + history[1] + 1;
        }
        // Maintain my history.
        history[0] = history[1];
        history[1] = result;
    }
    return result;
}

Answer 4

所以我终于能够解决它:(感谢所有的帮助，真的非常感谢）

public class Aufgabe1 {

// invokes iter as well as rec with all integers from 0 to 30 and prints the results
// (without empty lines or other output)
public static void main(String[] args) {
    // TODO: Implementation is your task
    int x = 0;
    while (x <= 30) {
        System.out.println(rec(x));
        x++;
    }
    long [] longArr = new long[31];
    iter(longArr);
}

public static int rec(int x) {
    if (x == 0) return 1;
    if (x == 1) return 1;
    else return rec(x - 1) + rec(x - 2) + 1;
}

    public static void iter(long[] n) {
        for (int i = 0; i < n.length; i++) {
            if (i == 0 || i == 1) {
                n[i] = 1;
            } else {
                n[i] = n[i - 1] + n[i - 2] + 1;
            }
            System.out.println(n[i]);
        }

    }
    }

将递归方法变成迭代方法

Turn a recursive method into an iterative method

java

iteration

algorithm

recursion