编写递归函数用来求斐波那契数列中第n项的值1,1,2,3,5,8,13,21
销魂军团丶傔
#includelong int fn(int);void main(){printf("%d",fn(10));}long int fn(int m){if ((1 == m) | (2 == m))temp = 1;elsetemp = fn(m - 1) + fn(m -2);}
为您推荐：
其他类似问题
扫描下载二维码C语言中 我要分别运用递推 和递推迭代法求FIBONACCI数列 求给同一个例子 编写两段程序且附上解释说明
回答的好 再加分
递归：int fun1(int n){if ( n == 1 || n == 2 ) return 1;return fun1(n - 1) +fun1(n - 2);}迭代：int fun2(int n){if ( n == 1 || n == 2 ) return 1;int tmpe,f1 = 1,f2 = 1;for (int i = 2; i
我要的是递推法不是递归法
我还要求旁边有注解说明
递推和递推迭代有区别吗？
按你的意思 应该就是
我写的第一个是迭代，第二个是递推吧。。。。
为您推荐：
其他类似问题
扫描下载二维码对尾递归的大概了解
服务器君一共花费了189.149 ms进行了4次数据库查询，努力地为您提供了这个页面。
试试阅读模式？希望听取您的建议
尾递归（tail recursive），看名字就知道是某种形式的递归。简单的说递归就是函数自己调用自己。那尾递归和递归之间的差别就只能体现在参数上了。
尾递归wiki解释如下：
尾部递归是一种编程技巧。递归函数是指一些会在函数内调用自己的函数，如果在递归函数中，递归调用返回的结果总被直接返回，则称为尾部递归。尾部递归的函数有助将算法转化成函数编程语言，而且从编译器角度来说，亦容易优化成为普通循环。这是因为从电脑的基本面来说，所有的循环都是利用重复移跳到代码的开头来实现的。如果有尾部归递，就只需要叠套一个堆栈，因为电脑只需要将函数的参数改变再重新调用一次。利用尾部递归最主要的目的是要优化，例如在Scheme语言中，明确规定必须针对尾部递归作优化。可见尾部递归的作用，是非常依赖于具体实现的。
我们还是从简单的斐波那契开始了解吧。
用普通的递归计算Fibonacci数列：
#include "stdio.h"
#include "math.h"
int factorial(int n);
int main(void)
printf("请输入斐波那契数n：");
scanf("%d",&n);
rs = factorial(n);
printf("%d \n", rs);
int factorial(int n)
if(n <= 2)
return factorial(n-1) + factorial(n-2);
程序员运行结果如下：
请输入斐波那契数n：20
Process returned 0 (0x0)
execution time : 3.502 s
Press any key to continue.
在i5的CPU下也要花费 3.502 秒的时间。
下面我们看看如何用尾递归实现数。
#include "stdio.h"
#include "math.h"
int factorial(int n);
int main(void)
printf("请输入斐波那契数n：");
scanf("%d",&n);
rs = factorial_tail(n, 1, 1);
printf("%d ", rs);
int factorial_tail(int n,int acc1,int acc2)
if (n < 2)
return acc1;
return factorial_tail(n-1,acc2,acc1+acc2);
程序员运行结果如下：
请输入斐波那契数n：20
Process returned 0 (0x0)
execution time : 1.460 s
Press any key to continue.
快了一倍有多。当然这是不完全统计，有兴趣的话可以自行计算大规模的值，这里只是介绍尾递归而已。
我们可以打印一下程序的执行过程，函数加入下面的打印语句：
int factorial_tail(int n,int acc1,int acc2)
if (n < 2)
return acc1;
printf("factorial_tail(%d, %d, %d) \n",n-1,acc2,acc1+acc2);
return factorial_tail(n-1,acc2,acc1+acc2);
程序运行结果：
请输入斐波那契数n：10
factorial_tail(9, 1, 2)
factorial_tail(8, 2, 3)
factorial_tail(7, 3, 5)
factorial_tail(6, 5, 8)
factorial_tail(5, 8, 13)
factorial_tail(4, 13, 21)
factorial_tail(3, 21, 34)
factorial_tail(2, 34, 55)
factorial_tail(1, 55, 89)
Process returned 0 (0x0)
execution time : 1.393 s
Press any key to continue.
从上面的调试就可以很清晰地看出尾递归的计算过程了。acc1就是第n个数，而acc2就是第n与第n+1个数的和，这就是我们前面讲到的“迭代”的精髓，计算结果参与到下一次的计算，从而减少很多重复计算量。
fibonacci(n-1,acc2,acc1+acc2)真是神来之笔，原本朴素的递归产生的栈的层次像二叉树一样，以指数级增长，但是现在栈的层次却像是数组，变成线性增长了，实在是奇妙，总结起来也很简单，原本栈是先扩展开，然后边收拢边计算结果，现在却变成在调用自身的同时通过参数来计算。
尾递归的本质是：将单次计算的结果缓存起来，传递给下次调用，相当于自动累积。
在Java等命令式语言中，尾递归使用非常少见，因为我们可以直接用循环解决。而在函数式语言中，尾递归却是一种神器，要实现循环就靠它了。
很多人可能会有疑问，为什么尾递归也是递归，却不会造成栈溢出呢？因为编译器通常都会对尾递归进行优化。编译器会发现根本没有必要存储栈信息了，因而会在函数尾直接清空相关的栈。
延伸阅读此文章所在专题列表如下：
本文地址：，欢迎访问原出处。
不打个分吗？
转载随意，但请带上本文地址：
如果你认为这篇文章值得更多人阅读，欢迎使用下面的分享功能。
小提示：您可以按快捷键 Ctrl + D，或点此 。
大家都在看
现代魔法研究协会欢迎你
阅读一百本计算机著作吧，少年
马丁(Robert C. Martin) (作者), 韩磊 (译者)
软件质量，不但依赖于架构及项目管理，而且与代码质量紧密相关。这一点，无论是敏捷开发流派还是传统开发流派，都不得不承认。《代码整洁之道》提出一种观念：代码质量与其整洁度成正比。干净的代码，既在质量上较为可靠，也为后期维护、升级奠定了良好基础。作为编程领域的佼佼者，《代码整洁之道》作者给出了一系列行之有效的整洁代码操作实践。这些实践在《代码整洁之道》中体现为一条条规则(或称“启示”)，并辅以来自现实项目的正、反两面的范例。只要遵循这些规则，就能编写出干净的代码，从而有效提升代码质量。
扫一扫，在手机上阅读
栏目最新博文
19,766 views
13,750 views
14,770 views
15,426 views
14,882 views
14,854 views
10,075 views
9,605 views
12,268 views
12,281 views
栏目博文推荐
4,740 views
5,462 views
15,443 views
12,281 views
7,133 views
9,842 views
14,882 views
11,623 views
5,414 views
5,793 views
去了解一个事物的本质，才可以征服该事物。
1,179 views
关于网站与作者
互联网信息太多太杂，各互联网公司不断推送娱乐花边新闻，SNS，微博不断转移我们的注意力。但是，我们的时间和精力却是有限的。这里是互联网浩瀚的海洋中的一座宁静与美丽的小岛，供开发者歇息与静心潜心修炼（愿景）。
“Veda”的本义是知识、启示，希望这里能为开发者提供充足的技术资料。
我的电子邮件gonnsai(，腾讯微博：，欢迎与我联系。斐波那契数列指的是这样一个数列：1、1、2、3、5、8、13、21、……
　&&这个数列从第三项开始，每一项都等于前两项之和。它的通项公式为：(1/√5)*{[(1&#43;√5)/2]^n -[(1-√5)/2]^n}（又叫“比内公式”，是用无理数表示有理数的一个范例。）（√5表示根号5）
&&&&有趣的是：这样一个完全是自然数的数列，通项公式居然是用无理数来表达的。
&&&&用数学公式表示出来就是：
&&&&&&&&&&F（1）=1，F（2）=1&&&&&(n=1,2)
&&&&&&&&&F(n)=F(n-1)&#43;F(n-2)&&&&&(n&2)
&&&&&有三种比较常用的求解第n项斐波那契数列的方法：递归法、迭代法、通项公式法。
概述　　递归做为一种算法在程序设计语言中广泛应用.是指函数/过程/子程序在运行过程中直接或间接调用自身而产生的重入现象.递归是计算机科学的一个重要概念,递归的方法是程序设计中有效的方法,采用递归编写程序能使程序变得简洁和清晰.。
　　程序调用自身的编程技巧称为递归（ recursion）。
　　一个过程或函数在其定义或说明中又直接或间接调用自身的一种方法，它通常把一个大型复杂的问题层层转化为一个与原问题相&#20284;的规模较小的问题来求解，递归策略只需少量的程序就可描述出解题过程所需要的多次重复计算，大大地减少了程序的代码量。递归的能力在于用有限的语句来定义对象的无限集合。一般来说，递归需要有边界条件、递归前进段和递归返回段。当边界条件不满足时，递归前进；当边界条件满足时，递归返回。
　　注意：
　　(1) 递归就是在过程或函数里调用自身;
　　(2) 在使用递归策略时，必须有一个明确的递归结束条件，称为递归出口。
　　递归的另一种定义：
　　递归，就是用自己的简单情况，定义自己。
　　在数学和计算机科学中，递归指由一种（或多种）简单的基本情况定义的一类对象或方法，并规定其他所有情况都能被还原为其基本情况。
　　例如，下列为某人祖先的递归定义：
　　某人的双亲是他的祖先（基本情况）。 某人祖先的双亲同样是某人的祖先（递归步骤）。斐波那契数列是典型的递归案例：
　　Fib(0) = 0 [基本情况] Fib(1) = 1 [基本情况] 对所有n &1的整数：Fib(n) = (Fib(n-1) &#43; Fib(n-2)) [递归定义]尽管有许多数学函数均可以递归表示，但在实际应用中，递归定义的高开销往往会让人望而却步。例如：
　　阶乘(1) = 1 [基本情况] 对所有n & 1的整数：阶乘(n) = (n *阶乘(n-1)) [递归定义]一种便于理解的心理模型，是认为递归定义对对象的定义是按照“先前定义的”同类对象来定义的。例如：你怎样才能移动100个箱子？答案：你首先移动一个箱子，并记下它移动到的位置，然后再去解决较小的问题：你怎样才能移动99个箱子？最终，你的问题将变为怎样移动一个箱子，而这是你已经知道该怎么做的。
　　如此的定义在数学中十分常见。例如，集合论对自然数的正式定义是：1是一个自然数，每个自然数都有一个后继，这一个后继也是自然数。
递归应用　　递归算法一般用于解决三类问题：
　　(1)数据的定义是按递归定义的。(Fibonacci函数)
　　(2)问题解法按递归算法实现。(回溯)
　　(3)数据的结构形式是按递归定义的。(树的遍历，图的搜索)
　　递归的缺点：
　　递归算法解题的运行效率较低。在递归调用的过程当中系统为每一层的返回点、局部量等开辟了栈来存储。递归次数过多容易造成栈溢出等。
这种方法的优点是简洁和容易理解，缺点是时间复杂度太大，随着n的增大，运算时间将会急剧增加。因此在很多场合这种方法是不可取的。
使用这种方法的关键代码是：
if(n == 1|| n== 2)
&&& return1;
&&& return fib(n- 1) &#43; fib(n - 2);
#include&stdio.h&
int main()
&&& longint& fib[41] = {0,1};
&&&for(i=2;i&41;i&#43;&#43;)
&&fib[i] =fib[i-1]&#43;fib[i-2];
&&&for(i=1;i&41;i&#43;&#43;)
&&printf(&F%d=%d\n&,i,fib[i]);
&&& return0;
这种方法相对于递归法来说在时间复杂度上减小了不少，但代码相对就要复杂些了。
#include&stdio.h&
int f(int n);
int main()
&&&scanf(&%d&,&n);
int f(int n)
&int i,f1=1,f2=1,f3;
&&printf(&输入错误.\n&);
&else if(n==1||n==2)
&&printf(&1&);
&&for(i=0;i&n-2;i&#43;&#43;)
&&&&&&&&&&&f3=f1&#43;f2;&&&&&&&&&&//f1表示当前的&#20540;
&&printf(&%d\n&,f1);
利用迭代算法解决问题，需要做好以下三个方面的工作：
&&&一、确定迭代变量。在可以用迭代算法解决的问题中，至少存在一个直接或间接地不断由旧&#20540;递推出新&#20540;的变量，这个变量就是迭代变量。
&&&二、建立迭代关系式。所谓迭代关系式，指如何从变量的前一个&#20540;推出其下一个&#20540;的公式（或关系）。迭代关系式的建立是解决迭代问题的关键，通常可以使用递推或倒推的方法来完成。
&&&三、对迭代过程进行控制。在什么时候结束迭代过程？这是编写迭代程序必须考虑的问题。不能让迭代过程无休止地重复执行下去。迭代过程的控制通常可分为两种情况：一种是所需的迭代次数是个确定的&#20540;，可以计算出来；另一种是所需的迭代次数无法确定。对于前一种情况，可以构建一个固定次数的循环来实现对迭代过程的控制；对于后一种情况，需要进一步分析出用来结束迭代过程的条件。
3、通项公式法
这种方法是最没技术含量的方法，只要你知道通项公式照着把它翻译成编程语言就可以了，优点不言而喻。
fib(n) = pow(((1 &#43; sqrt(5)) / 2.0),n) / sqrt(5) - pow(((1 -sqrt(5)) / 2.0),n) / sqrt(5));
&&&&这三种方法各有优缺点，使用哪种方法根据实际情况确定。
&&&从时间复杂度上来说O(通向公式法)&O(迭代法)&O(递归法)。
参考知识库
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：745次
排名：千里之外}