递归优化

Posted on Edited on In

递归优化

原因：

在 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)

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

参考资料：