Java中尾递归
2020-03-22 16:02:53来源:博客园 阅读 ()
Java中尾递归
在以往解决需要递归求解的问题上一直使用传统递归,而不久前老师讲解了尾递归感觉需要记录一下(好记性不如烂笔头)
尾递归特点:在普通尾调用上,多出了2个特征。
1.在尾部调用的是函数自身(Self-called)
2.可通过优化,使得计算仅占常量栈空间(Stack Space)
举个例子:
斐波那契数列(Fibonacci sequence),又称黄金分割数列、因数学家列昂纳多·斐波那契(Leonardoda Fibonacci)以兔子繁殖为例子而引入,故又称为“兔子数列”,指的是这样一个数列:1、1、2、3、5、8、13、21、34、……在数学上,斐波纳契数列以如下被以递推的方法定义:F(1)=1,F(2)=1, F(n)=F(n-1)+F(n-2)(n>=3,n∈N*)在现代物理、准晶体结构、化学等领域,斐波纳契数列都有直接的应用。
下面代码仅求斐波那契数列的第n项为多少,而不求前n项和。
1 public class Fibonacci { 2 3 public static void main(String[] args) { 4 int n = 50; 5 long begin1 = System.currentTimeMillis(); 6 System.out.printf("%d\n", fibonacci(n)); 7 long end1 = System.currentTimeMillis(); 8 System.err.println("花费时间:" + (end1 - begin1) + "毫秒"); 9 10 long begin2 = System.currentTimeMillis(); 11 System.out.printf("%d\n", advanced(n, 0L, 1L)); 12 long end2 = System.currentTimeMillis(); 13 System.err.println("花费时间:" + (end2 - begin2) + "毫秒"); 14 } 15 16 static long fibonacci(int n) { 17 if (n < 0) 18 return -1; 19 if (n <= 1) 20 return n; 21 return fibonacci(n - 1) + fibonacci(n - 2); 22 } 23 24 static long advanced(int n, long ret1, long ret2) { 25 if (n < 0) 26 return -1; 27 if (n == 0) 28 return ret1; 29 if (n == 1) 30 return ret2; 31 return advanced(n - 1, ret2, ret1 + ret2); 32 } 33 34 }
结果显示:
计算fibonacci数列第50项。
一些初学的想法:传统的递归相当于树状图计算,而尾递归相当于循环计算
譬如计算数字阶乘时:假设计算8!,传统递归理解为8*7*6*5*4*3*2*Factorial(1);递归函数中留有出口,直到递归到出口参数为1时才返回值。
尾递归相当于循环计算,我看做为循环递归。计算8!就循环8次。函数形如:
static long advanced(int n, int r) { if (n < 0) { return -1; } else if (n == 0) { return 1 * r; } else { return advanced(n - 1, r * n); } }
其中第一个参数为循环递归次数,第二个参数为每一步循环计算出的数,作为新的参数继续进行递归。(简单来说就是算出阶乘的每一步值作为新的参数)
函数返回自身函数,计算最终答案,进行下一函数计算时,不在依赖于上一函数,减少了栈空间的开辟。
ps:感觉类似于一串数的正反相乘过程。
原文链接:https://www.cnblogs.com/singularity123/p/12545884.html
如有疑问请与原作者联系
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
- 国外程序员整理的Java资源大全(全部是干货) 2020-06-12
- 2020年深圳中国平安各部门Java中级面试真题合集(附答案) 2020-06-11
- 2020年java就业前景 2020-06-11
- 04.Java基础语法 2020-06-11
- Java--反射(框架设计的灵魂)案例 2020-06-11
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash