递归优化
递归优化
原因:
在 Java 中,每个线程都有独立的 Java 虚拟机栈。栈具有后入先出的特点,递归调用也是需要后调用的方法先返回,因此使用栈来存储递归调用的信息。这些信息存储在栈帧中,每个 Java 方法在执行时都会创建一个栈帧,用来存储局部变量表、操作数栈、常量池引用等信息。在调用方法时,对应着一个栈帧入栈,而方法返回时,对应着一个栈帧出栈。
随着栈帧frame的增多,将会导致Stack Overflow的报错,例如
int f(int i)
{
if(i == 1 || i == 2)
return 1;
else
return (f(i - 1) + f(i - 2));
}
解决方法1:递归–>非递归
其实很简单,就是用一个临时变量,来保存中间的值,而不是压入堆栈中,
//费波纳列数列,前两位是1,之后没位数是前两位数的和
private static void fibonacci(int n) {
int temp1=1,temp2=1,temp;
for (int i = 1; i <=n ; i++) {
temp=temp1+temp2;
temp1=temp2;
temp2=temp;
}
System.out.println();
}
//粘贴于网上
解决办法2:递归–>尾递归
尾递归就是当函数在最后一步(尾部)调用自身,如:
function f(x){
return g(x);
}
以下算法来自阮一峰教程:
function factorial(n) {
if (n === 1) return 1;
return n * factorial(n - 1);
}
factorial(5) // 120
该算法并非是尾递归,因为其在返回值的时候进行了一个乘法操作,所以还是普通的递归,复杂度为O(n),而如果改成尾递归,则:
function factorial(n, total) {
if (n === 1) return total;
return factorial(n - 1, n * total);
}
factorial(5, 1) // 120
该算法只需要计算
factorial(5,1)
factorial(4,5)
factorial(3,20)
factorial(2,60)
factorial(1,120)
在进入新的递归函数时,尾递归不再需要使用栈帧保存数据,允许抛弃旧的栈帧,那么只需要保存一个栈帧即可