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