递归算法详解及经典例题（C语言）

比眉伴天荒 2022-04-23 09:30 387阅读 0赞

1.递归：在定义一个过程或者函数时出现调用本身或本函数的成分。若调用自身，则称之为直接递归；若过程或者函数P调用过程或者函数Q，而Q又调用P，称之为间接递归，所有的间接递归都可以转换为直接递归，在此，我们只讨论间接递归。我们将包含递归过程的算法称之为递归算法。**尾递归**是指递归调用语句只有一个而且是处于算法的末尾，例如我们即将提到的求解n!的算法就是尾递归算法。经过分析可知，当递归调用返回时，返回到上一层再递归调用的下一语句，而这个位置正好是算法的末尾。也就是说，以前每次递归调用时保存的返回值地址。函数返回值、函数参数等实际上在这里根本没有被使用。因此，对于尾递归形式的算法，不必利用系统运行时的栈保存各种信息。尾递归形式的算法实际上可变成循环结构的算法。**递归算法的缺点**：由于递归算法在堆栈中执行，那么如果出现递归调用过多，以至于将堆栈内存沾满，后果将不堪设想。因此我们可以将一些没必要递归或者递归调用可能过多的算法转变为非递归算法。循环结构求解n!问题的算法如下：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NjE0NTI0_size_16_color_FFFFFF_t_70]  
实际上，采用*循环结构消除递归没有通用的转换算法*，对于具体问题要深入分析对应的递归结构，设计有效的循环语句地轨道非递归的转换。  
2.递归思路就是将一个不好或不能直接求解的“大问题”转化成一个或几个“小问题”来解决，再将这些“小问题”进一步分解为更小的“小问题”来解决，如此进行，直到每个“小问题”都可以直接解决（此时问题已经被分解至递归出口）。在分解的时候要注意：*“大问题”与“小问题”要相似，即两者的求解环境与过程都相似*。  
3.***递归算法的设计***：递归的求解过程均有这样的特征：先将整个问题划分为若干个子问题，通过求解若干个子问题，最后获得整个问题的解。而这些子问题具有与原问题相同的求解办法，于是可以将他们再次划分为若干个子问题，分别进行求解，如此反复进行，直到不能再次划分为子问题或者可以求解为止。这种自上而下将问题分解、求解，在自上而下引用、合并，求出最后的解答的过程称之为递归求解过程，**这是一种分而治之的算法设计方法**。  
4.*如果一个递归过程或递归函数中递归调用语句是最后一条执行语句，则称这种递归为尾递归*。举例如下：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NjE0NTI0_size_16_color_FFFFFF_t_70 1]  
将上图中的代码用递归模型写出来如下：  
fun(1) = 1 (1)  
fun(n) = n \* fun(n - 1) n > 1 (2)  
其中，第一个式子给出了递归的终止条件，第二个式子给出了f(n)的值与f(n - 1)的值之间的关系。  
5.简单的递归算法的图解  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NjE0NTI0_size_16_color_FFFFFF_t_70 2]  
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项的值。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NjE0NTI0_size_16_color_FFFFFF_t_70 3]  
（二 ）递归的计算n的阶乘  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NjE0NTI0_size_16_color_FFFFFF_t_70 4]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NjE0NTI0_size_16_color_FFFFFF_t_70]: /images/20220321/ff517dfab4cc465aa5b692a3d0cfff9f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NjE0NTI0_size_16_color_FFFFFF_t_70 1]: /images/20220321/0954d54c6b284fa793ca55da415dac14.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NjE0NTI0_size_16_color_FFFFFF_t_70 2]: /images/20220321/9ba8a3462d22478ebbcacf42aab4399b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NjE0NTI0_size_16_color_FFFFFF_t_70 3]: /images/20220321/faf0bf66a87347a9a677e438337f12d5.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NjE0NTI0_size_16_color_FFFFFF_t_70 4]: /images/20220321/ea6936087ffa4a41815861d0d57f0515.png