尾递归优化小记
前言
一般地,对于java语言而言,普通的递归调用是在java虚拟机栈上完成的.假如a()是一个递归方法,那么在其内部再调用自己的时候,假设为a1(),那么a1()方法变量表将创建在a()方法栈帧之上,从而形成了一个新的栈帧.因此容易发现,在递归思想中,递归简化了问题的表达,但牺牲了虚拟机栈中的内存空间.
普通递归
斐波那契递归法
public static int fib(int num){ if(num<2) return num; else return fib(num-2)+fib(num-1); }
- 对于上面的解法,很容易就会发现,不但属于普通递归,而且在计算fib(num-1)是重复了fib(num-2)的计算量,因此代码效率大打折扣.因此效率较高的写法可以用for循环计算,
public static int fib3(int n) { if (n < 2) return n; else { int pre = 0; int suf = 1; for (int i = 2; i <= n; i++) { int temp = suf; suf += pre; pre = temp; } return suf; } }
斐波那契尾递归优化
public class Main { public static void main(String[] args) { System.out.print(fib2(3, 0, 1)); } public static int fib2(int count, int pre, int result) { if (count == 1) return result; else return fib2(--count, result, result + pre); } }
性能对比
public static void main(String[] args) { long time = new Date().getTime(); int num=40; System.out.println(fib(num)); System.out.println("普通递归调用用时:" + (new Date().getTime() - time) + "毫秒"); time = new Date().getTime(); System.out.println(fib2(num, 0, 1)); System.out.println("尾递归优化调用用时:" + (new Date().getTime() - time) + "毫秒"); time = new Date().getTime(); System.out.println(fib3(num)); System.out.println("for循环法调用用时:" + (new Date().getTime() - time) + "毫秒"); } //输出 /* 102334155 普通递归调用用时:674毫秒 102334155 尾递归优化调用用时:0毫秒 102334155 for循环法调用用时:0毫秒 */
- 可以看出有明显差异,即使普通递归法计算量多了一半,时间除以2也是387毫秒,这也远远高于for循环和递归尾优化法.
尾递归优化思想
- 即递归方法return 直接返回方法,注意是直接返回方法,不能是方法加1个值等形式.这样在递归调用时,新方法会覆盖当前栈帧,达到节省栈空间的目的.因此也就不会有递归调用产生的栈溢出问题.
尾递归写法
斐波那契例:
//count作为计数,表示递归层次, //pre代表前一个值 //result 表示当前值 public static int fib2(int count, int pre, int result) { //层次减到1时返回计算结果 if (count == 1) return result; else{ //递归调用时,层次减1,前一项更新为当前项,所以填result,第三个参数即实现了倒数第二个参数加倒数第一个参数. return fib2(--count, result, result + pre); } }
- 总体而言参数的书写分为两部分
- 前部分为计数,后部分为计算,例如计算阶乘时候只需要两个参数,第一个计数,第二个存结果.
- 尾递归将全部信息放入了参数里,因此也就巧妙地避免了需要上一栈帧保存信息.
原文地址:https://segmentfault.com/a/1190000018448766
相关推荐
-
Mybatis结合Oracle的foreach insert批量插入报错! Java基础
2020-7-7
-
你不知道的System.out.println() Java基础
2020-5-30
-
Java多线程同步工具类之CyclicBarrier Java基础
2019-9-6
-
一致性Hash算法 Java基础
2019-10-8
-
详解java并发包源码之AQS独占方法源码分析 Java基础
2020-5-30
-
前后端分类如何使用JWT实现用户身份认证问题以及如何实现单点登录 Java基础
2019-10-2
-
动态规划实现最优二分搜索树 Java基础
2019-7-25
-
LinkedList 源码分析(JDK 1.8) Java基础
2019-6-26
-
JVM源码分析之新生代DefNewGeneration的实现 Java基础
2018-3-20
-
避免自己写的 url 被diss!建议看看这篇RestFul API简明教程! Java基础
2020-6-18