0%

递归优化

原因:

在 Java 中,每个线程都有独立的 Java 虚拟机栈。栈具有后入先出的特点,递归调用也是需要后调用的方法先返回,因此使用栈来存储递归调用的信息。这些信息存储在栈帧中,每个 Java 方法在执行时都会创建一个栈帧,用来存储局部变量表操作数栈常量池引用等信息。在调用方法时,对应着一个栈帧入栈,而方法返回时,对应着一个栈帧出栈。

img

随着栈帧frame的增多,将会导致Stack Overflow的报错,例如

1
2
3
4
5
6
7
int f(int i)
{
if(i == 1 || i == 2)
return 1;
else
return (f(i - 1) + f(i - 2));
}

解决方法1:递归–>非递归

其实很简单,就是用一个临时变量,来保存中间的值,而不是压入堆栈中,

1
2
3
4
5
6
7
8
9
10
11
//费波纳列数列,前两位是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:递归–>尾递归

尾递归就是当函数在最后一步(尾部)调用自身,如:

1
2
3
function f(x){
return g(x);
}

以下算法来自阮一峰教程:

1
2
3
4
5
6
function factorial(n) {
if (n === 1) return 1;
return n * factorial(n - 1);
}

factorial(5) // 120

该算法并非是尾递归,因为其在返回值的时候进行了一个乘法操作,所以还是普通的递归,复杂度为O(n),而如果改成尾递归,则:

1
2
3
4
5
6
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)

在进入新的递归函数时,尾递归不再需要使用栈帧保存数据,允许抛弃旧的栈帧,那么只需要保存一个栈帧即可

参考资料: