首页 > 代码库 > C自学笔记-递归与迭代的使用方法笔记与两者的使用场合
C自学笔记-递归与迭代的使用方法笔记与两者的使用场合
递归和迭代在刚开始学C语言的时候就学过,但是不知道怎么使用。今天遇到一个题目分析过后
我瞬间想起来之前学过递归的方法,做完题后顺便翻了翻书整理了这个笔记。题目大概是这样的。
题目:猴子吃桃问题:猴子第一天摘下若干个桃子,当即吃了一半,还不瘾,又多吃了一个
第二天早上又将剩下的桃子吃掉一半,又多吃了一个。以后每天早上都吃了前一天剩下
的一半零一个。到第10天早上想再吃时,见只剩下一个桃子了。求第一天共摘了多少。
实力分析一波:
1:1
2:(1+1)*2
3:(n2+1)*2
10:(n9+1)*2
用递归:
int taozi(int i)
{
int sum;
if(i>1) sum = taozi(i-1)*2;
else sum=1;
return sum;
}
总结:
1:递归一定要有结束条件作为返回;
2:递归的逻辑即将一个大的问题分解成一个一个越来越小的相同的问题 从而做到以小解大;
如上一题的n10=n9*+1 ······ n1=1;如阶乘的 n=(n-1)*(n-2).....*1;
3:K&A说过:由于递归会使用到堆栈来保存各层嵌套的局部变量,
这种浪费和低效率是优化代码无法解决的。所以效率会比较低;所以当
层级关系较为简单时用迭代是更好的选择;如阶乘这样的关系既可以迭代来做:
求n阶乘
for(value=http://www.mamicode.com/1,i=0;i<=n;i++)
{
value *= n;
}
再比如:1+2!+3!+4!+...+n!=?
for(sum=0,t=1,i=1;i<=n;i++)
{
t *= i;
sum += sum*t;
}
当求斐波那契级数是使用递归时由于n=(n-1)+(n-2)那么造成的堆栈浪费和低效率将会更可怕;
K&A还提到:用递归的方法求这类问题时可以使代码量较少且直观,迭代法效率高但代码可读性可能比前者差,程序员要对代码的可读和效率做权衡后再选择使用。
C自学笔记-递归与迭代的使用方法笔记与两者的使用场合