递归算法中的奇怪行为,
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 方法的基本调用。这将最终导致斐波那契方法的多次调用。
在我看来,循环在您的递归解决方法中没有意义。
我正在编写一个递归算法来计算 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 方法的基本调用。这将最终导致斐波那契方法的多次调用。
在我看来,循环在您的递归解决方法中没有意义。