JAVA:斐波那契递归和非递归函数

Question

您好，很抱歉这个菜鸟问题。我是 Mario，请问我的程序对于斐波那契数列第 n 个值的递归和非递归函数是否正确。

static int recursiveMethod(int num) 
{ 
if (num <= 1) 
   return num; 
return recursiveMethod(num-1) + recursiveMethod(num-2); 
}

static int nonRecursiveMethod(int num) { 
    if (num == 0) { 
        return 0; 
    }

    if (num == 1) {
        return 1; 
    } 
    int first = 0; 
    int second = 1; 
    int nth = 1; 
    for (int i = 2; i <= num; i++) { 
        nth = first + second;
        first = second;
        second = nth;
    } 
    return nth;
}

总结:示例 我输入 6 作为我的第 n 个值。然后输出是递归:然后是 8非递归:1 1 2 3 5 8

正确吗？

Answer 1

调用 nonRecursiveMethod 将产生与调用 recursiveMethod 相同的输出。结果是正确的，但是 recursiveMethod 对于大数来说效率低下，因为它会一次又一次地计算较小数的结果。