为什么迭代会消耗大量的CPU资源,解决的办法是什么?

huangCF 发布于 2016/06/18 13:48
阅读 689
收藏 0
public static void main(String[] args) {
while(true){
Scanner scan = new Scanner(System.in);
System.out.println("请输入月份");
System.out.println("当前月兔子的总数为:"+sum(scan.nextLong()));
}
}
public static long sum(long month){
if(month==1||month==2){
return 1;
}else{
return sum(month-1)+sum(month-2);
}

}

计算100个兔子把我的电脑都快搞残了,这说明什么?


加载中
0
zabcd117
zabcd117

可以把普通的线性递归改成尾递归或者循环来减少堆栈的调用。

//尾递归
function sum1(n, a, b){
  if (n==0) {
    return a; 
  } else {
  return sum1(n-1, b, a+b);
  }
}
console.log(sum1(1000,0,1));
//循环
function sum2(n){
  var arr = [0,1,1];
  if(n<=2) {
    return arr[n];
  }
  var k = 3;
  while(k <= n){
    arr.push(arr[k-1]+arr[k-2]);
    k++;
  }
  return arr[k-1];
}
console.log(sum2(1000));



直接到浏览器的控制台跑一下吧,java的同理。可以看下这篇文章的介绍就差不多明白了。https://zh.wikipedia.org/wiki/%E5%B0%BE%E8%B0%83%E7%94%A8

h
huangCF
感谢
0
刘柳
刘柳
每次递归方法的调用都会分配一个新的调用堆栈,大小默认是2k,你算一下你分配了多少个!
h
huangCF
400k吗?
0
刘柳
刘柳
2的100次方-1
h
huangCF
好难算啊( ⊙ o ⊙ )
0
xpbob
xpbob
主要你是用了递归,想要减小的话,就递归转非递归程序,所有的递归都可以用非递归转化
0
__c
__c
可以缓存一下结果。每次计算都把计算结果保存起来,调用时如果发现之前有进行过相同的计算就直接返回结果。虽然还是不如不用递归的快,但是比较直观
0
中山野鬼
中山野鬼

引用来自“xpbob”的评论

主要你是用了递归,想要减小的话,就递归转非递归程序,所有的递归都可以用非递归转化

这个观点赞一个。至于楼上说什么尾调用,客观说一句“不待主观情绪”,这个概念纯粹没事找事 。。。。安心改称非递归是正途,不要过度关注编译器对函数调用的优化工作。哈

额外喷一句,最早提出尾调用的人,咋当初不提一下长跳转,哈。岂不是更皆大欢喜。结果呢?结果恐怕只会把算法搞的更凌乱。。

中山野鬼
中山野鬼
回复 @jQer : lisp不懂,特别是它的编译系统前端的工作机制,不好讨论。哈。 c也好,c++,java之类的也好,递归是要绕过去的东西。更不用说尾递归了。反正不是用递归构造代码,总是应该的,除非某个语言的编译器专门针对递归有特定的优化,就是方便于递归方式描述问题。哈。
jQer
jQer
这个观点,我觉得不敢苟同了。正如那篇亚马逊工程师评价语言中写的,尾递归是为了描述计算用的,在 Lisp 机器之类的函数式系统中诞生的。Java C 这些语言扯到尾递归,纯属自己的好事者所谓。尾递归也很简单,写个尾递归宏编译成循环就可以。尾递归的价值在于容易描述嵌套循环。
返回顶部
顶部