递归算法详解及经典例题（C语⾔）
1.递归：在定义⼀个过程或者函数时出现调⽤本⾝或本函数的成分。若调⽤⾃⾝，则称之为直接递归；若过程或者函数P调⽤过程或者函数Q，⽽Q⼜调⽤P，称之为间接递归，所有的间接递归都可以转换为直接递归，在此，我们只讨论间接递归。我们将包含递归过程的算法称之为递归算法。尾递归是指递归调⽤语句只有⼀个⽽且是处于算法的末尾，例如我们即将提到的求解n!的算法就是尾递归算法。经过分析可知，当递归调⽤返回时，返回到上⼀层再递归调⽤的下⼀语句，⽽这个位置正好是算法的末尾。也就是说，以前每次递归调⽤时保存的返回值地址。函数返回值、函数参数等实际上在这⾥根本没有被使⽤。因此，对于尾递归形式的算法，不必利⽤系统运⾏时的栈保存各种信息。尾递归形式的算法实际上可变成循环结构的算法。递归算法的缺点：由于递归算法在堆栈中执⾏，那么如果出现递归调⽤过多，以⾄于将堆栈内存沾满，后果将不堪设想。因此我们可以将⼀些没必要递归或者递归调⽤可能过多的算法转变为⾮递归算法。循环结构求解n!问题的算法如下：
实际上，采⽤循环结构消除递归没有通⽤的转换算法，对于具体问题要深⼊分析对应的递归结构，设计有效的循环语句地轨道⾮递归的转换。
2.递归思路就是将⼀个不好或不能直接求解的“⼤问题”转化成⼀个或⼏个“⼩问题”来解决，再将这些“⼩问题”进⼀步分解为更⼩
的“⼩问题”来解决，如此进⾏，直到每个“⼩问题”都可以直接解决（此时问题已经被分解⾄递归出⼝）。在分解的时候要注意：“⼤问题”与“⼩问题”要相似，即两者的求解环境与过程都相似。
3.递归算法的设计：递归的求解过程均有这样的特征：先将整个问题划分为若⼲个⼦问题，通过求解若⼲个⼦问题，最后获得整个问题的解。⽽这些⼦问题具有与原问题相同的求解办法，于是可以将他们再次划分为若⼲个⼦问题，分别进⾏求解，如此反复进⾏，直到不能再次划分为⼦问题或者可以求解为⽌。这种⾃上⽽下将问题分解、求解，在⾃上⽽下引⽤、合并，求出最后的解答的过程称之为递归求解过程，这是⼀种分⽽治之的算法设计⽅法。
4.如果⼀个递归过程或递归函数中递归调⽤语句是最后⼀条执⾏语句，则称这种递归为尾递归。举例如下：
将上图中的代码⽤递归模型写出来如下：
fun(1) = 1 (1)
fun(n) = n * fun(n - 1) n > 1 (2)
其中，第⼀个式⼦给出了递归的终⽌条件，第⼆个式⼦给出了f(n)的值与f(n - 1)的值之间的关系。c语言斐波那契数列
5.简单的递归算法的图解
6.经典例题：斐波那契数列（Fibonacci Sequence），⼜称黄⾦分割数列，指的是这样⼀个数列：1、1、2、3、5、8、13、21、……。在数学上，斐波纳契数列以递推的⽅法定义为：F(1)=1，F(2)=1，F(n)=F(n-1)+F(n-2)（n≥2，n∈N）。
（⼀）递归计算斐波那契数列第n项的值。
（⼆ ）递归的计算n的阶乘

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。