我在 Java 中的递归方面遇到了一些问题。 这是我的代码
public class recursionTrial {
public static void main(String[] args)
{
System.out.println(doSomething(6));
}
public static int doSomething(int n)
{
if (n==0 || n==1)
return 0;
else
return n + doSomething(n-1) + doSomething(n-2);
}
}
这给了我 38 的输出。但是我无法在我的头脑或纸上追踪递归函数。锻炼效果如何? 6+5......等等。
我知道如果只是这样
return n + doSomething(n-1)
那么就是 6+5+4+3+2 = 20 ;这是令我困惑的代码的第二部分。如果有人可以向我解释如何正确跟踪递归函数并编写计算结果,我将不胜感激!还有一种方法可以编写一段代码,在每次更改之前打印 n 的值?
最佳答案
在没有副作用的情况下,我们可以将此递归函数视为常规函数。您可以绘制一个小表,显示函数调用的结果,从零开始:
n res computation
- --- -----------
0 0 0
1 0 0
2 2 2+0+0
3 5 3+2+0
4 11 4+5+2
5 21 5+11+5
6 38 6+21+11
第二次递归调用不需要特殊的心理处理:它与第一次相同。
注意:随着 n
值的增加,您的函数将花费越来越长的时间,因为它将重新执行大量已经完成的计算。幸运的是,这个问题可以通过一个简单且非常常见的技巧来解决,称为 memoization .
关于java - 2 Java中函数的递归调用,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/30286345/