递归算法中的奇怪行为,

Strange behavior in recursive algorithm,

我正在编写一个递归算法来计算 Java 中的斐波那契数,作为编程 101 课程的一部分。这是代码:

public class Fib {

    public static void main(String[] args) {
        Fib fib = new Fib();
    }

    public Fib() {
        int end = 9;
        long[] nums = new long[2];
        printFib(0, end, nums);
    }

    private void printFib(int i, int end, long[] nums) {
        while(i < end) {
            if(i == 0 || i == 1) {
                nums[i] = 1;
                System.out.println("1");
            } else {
                long fib;
                fib = 0;
                fib += (nums[0] + nums[1]);
                nums[0] = nums[1];
                nums[1] = fib;
                System.out.println(fib);    
            }
            i++;
            printFib(i, end, nums);
        }
    }
}

当我逐步执行程序时,它按预期工作,直到 i 等于 end,该变量告诉 printFib 方法它应该打印出多少斐波那契数.当 ì 等于 end while(i < 1) return 如预期的那样为 false 并且程序转到最后一个 },现在你(我) 期望程序 return 我最初从中调用函数的构造函数并且程序应该退出,但事实并非如此。该程序返回到 while 语句并以某种方式再次评估为 false。然后它再次做同样的事情,除了第二次将 i 减 1(什么?!),然后在到达 if 语句时继续执行 else 子句。然后它一遍又一遍地做同样的事情,交替从 i 中减去 1 和 2 之间的数量。我已经问过我的老师这件事,他无法解释。

如果我将 while 替换为 if,该程序将完全按照我的预期工作,所以可能 while 有一些我不知道的地方。

编辑 所以我现在意识到每次调用方法时 i 都有一个不同的值被存储,当方法退出并且 i = end 程序返回到我之前的调用有不同的价值。

您实现了一个迭代算法来计算斐波那契数列。这就是 while 循环的作用。最后进行递归调用 - printFib(i, end, nums) 毫无意义。

如果您打算递归实现,则不需要整个 while 循环。

我觉得这段代码不对。

我建议您不要使用您的方法进行打印。 Return 给 main 一个值,让它打印出来。

您的递归方法中不应包含 while 循环。这就是迭代 - 正是您在这里要避免的。

您的方法应该有一个停止条件和一个对自身的调用。那不是你在做什么。

这样想:

/**
 * Recursive Fibonnaci
 * User: mduffy
 * Date: 2/11/2015
 * Time: 8:50 AM
 * @link 
 */
public class Math {

    private static Map<Integer, Integer> memo = new ConcurrentHashMap<Integer, Integer>();

    public static void main(String [] args) {
        for (String arg : args) {
            int n = Integer.valueOf(arg);
            System.out.println(String.format("n: %d fib(n): %d", n, fibonnaci(n)));
        }
    }

    public static int fibonnaci(int n) {
        if (n < 0) throw new IllegalArgumentException("index cannot be negative");
        int value = 0;
        if (memo.containsKey(n)) {
            value = memo.get(n);
        } else {
            if (n <= 1) {                
                value = n;
            } else {
                value = fibonnaci(n-1)+fibonnaci(n-2);
            }
            memo.put(n, value);
        }
        return value;
    }
}

基本上发生这种情况是因为我猜您将 i 视为参考,这将影响调用子 Fibunacci 方法的 Fibunacci 方法的基本调用。这将最终导致斐波那契方法的多次调用。

在我看来,循环在您的递归解决方法中没有意义。