【算法与数据结构 11】递归算法，看这一篇就够了！

分手后的思念是犯贱 2022-12-12 04:35 66阅读 0赞

> 大家好！我是【AI 菌】，一枚爱弹吉他的程序员。我`热爱AI、热爱分享、热爱开源`！ 这博客是我对学习的一点总结与思考。如果您也对 `深度学习、机器视觉、算法、Python、C++` 感兴趣，可以关注我的动态，我们一起学习，一起进步~  
> 我的博客地址为：[【AI 菌】的博客][AI]  
> 我的Github项目地址是：[【AI 菌】的Github][AI _Github]

### 文章目录 ###

*   *  一、递归的原理
     *  二、递归的算法思想
     *  三、建立递推公式
     *  四、建立递推关系
     *   *  4.1 简单示例：反向打印字符串
         *  4.2 简单示例：反转字符串
     *   养成习惯，先赞后看！你的支持是我创作的最大动力！

我们都知道，不管是数据结构还是算法，它们的目标都是**降低时间复杂度**。数据结构是从**数据组织形式**的角度达成这个目标，而算法思维则是从**数据处理**的思路上去达成这个目标。

在前面的系列文章中，我们已经学习了各种**数据结构**的基础知识：

[【算法与数据结构 04】多图讲解——线性表、顺序表、链表][04]  
[【算法与数据结构 05】后进先出的栈——顺序栈、链栈知多少?][05]  
[【算法与数据结构 06】先进先出的队列 —— 顺序队列 || 循环队列 || 链式队列 大盘点][06_ _ _ _ _ _ _]  
[【算法与数据结构 07】数组 —— 数组的基本操作( 增删查与时间复杂度的关系！)][07_ _ _]  
[【算法与数据结构 08】字符串 —— 字符串匹配算法（面试高频考点！）][08_ _]  
[【算法与数据结构 09】什么是树、二叉树、二叉查找树？][09]  
[【算法与数据结构 10】哈希表——高效查找的利器][10]

从今天开始，我们将开启**算法思维**的学习之路。下面，我们就来学习最常用的算法思维之一 —— **递归**。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dqaW5qaWU_size_16_color_FFFFFF_t_70_pic_center]

--------------------

## 一、递归的原理 ##

在数学与计算机科学中，递归 （Recursion）是指**在函数的定义中使用函数自身的方法**。直观上来看，就是**某个函数自己调用自己**。

递归有两层含义：

*  递归问题必须可以**分解为**若干个规模较小、与原问题形式相同的**子问题**。并且这些子问题可以用**完全相同**的解题思路来解决；
 *  递归问题的演化过程是一个对原问题从**大到小进行拆解**的过程，并且会有一个明确的**终点**。最后，从这个终点开始，把小问题的答案按照**原路返回**，原问题便得以解决。

简而言之，递归的基本思想就是把规模大的问题转化为规模小的相同的子问题来解决。 在函数实现时，因为大问题和小问题是一样的问题，因此大问题的解决方法和小问题的解决方法也是同一个方法。这就产生了函数调用它自身的情况，这也正是递归的定义所在。

总之，递归的实现包含了两个部分：

*  **递归主体**。是解决若干相同子问题的主要思路。
 *  **终止条件**。解决问题的函数必须有明确的结束条件，否则就会导致无限递归的情况

![在这里插入图片描述][20201005225125983.jpg_pic_center]

--------------------

## 二、递归的算法思想 ##

递归的数学模型其实就是**数学归纳法**，这个证明方法是我们高中时期解决数列问题最常用的方法。接下来，我们通过一道题目简单回顾一下数学归纳法。

> 一个常见的题目是：证明当 n 等于任意一个自然数时某命题成立。

当采用数学归纳法时，证明分为以下两个步骤：

*  证明当 n = 1 时命题成立；
 *  假设 n = m 时命题成立，那么尝试推导出在 n = m + 1 时命题也成立。

与数学归纳法类似，当采用递归算法解决问题时，我们也需要围绕这两个步骤去做：

*  当你面对一个大规模问题时，如何把它分解为几个小规模的同样的问题；
 *  当你把问题通过多轮分解后，最终的结果，也就是终止条件如何定义。

以上就是递归的算法思想。我们总结一下，写出递归代码的关键在于，写出**递归主体**和找出**终止条件**。

对于递归主体，一般有两种形式：**递推公式**和**递推关系**。

*  对于一些数学逻辑关系明显，能用公式表达的问题，可采用递推公式。
 *  对于一些不易用公式表达的问题，要尽量发掘问题中的逻辑，用递推关系表示。

--------------------

## 三、建立递推公式 ##

对于一些数学逻辑关系明显的问题，我们采用 **递推公式 + 终止条件** 的方式来解决。下面以一道简单的题目为例：

> 已知Fibonacci数列为：1、1、2、3、5、8…，求Fibonacci数列的第n个数是多少？

经过观察，根据Fibonacci数列的规律，我们很容易知道：数列当前项的值等于前两项之和。用数学公式表示为：

F ( n ) = F ( n − 1 ) + F ( n − 2 ) ， 其 中 F ( 1 ) = F ( 2 ) = 1 。 F(n)=F(n-1)+F(n-2)，其中F(1)=F(2)=1。 F(n)=F(n−1)\+F(n−2)，其中F(1)=F(2)=1。

由此可知，当我们采用递归的方法来做时。递推公式已经得到：F(n)=F(n-1)+F(n-2)；而终止条件就是：F(1)=F(2)=1。

递推公式和终止条件都已经得出，下面就可以用代码表示出来了：

#include <iostream>
    using namespace std;
    
    //Fibonacci数列函数 
    int Fibonacci(int n)   
    { 
    	if(n==1||n==2)
    		return 1;
    	else
    		return Fibonacci(n-1)+Fibonacci(n-2);
    }
    
    int main()
    { 
    	int n=0;
    	cin>>n;
    	//输出Fibonacci数列第n个数 
    	cout<<Fibonacci(n);  
    	return 0;
    }

以上就是 **递推公式 + 终止条件** 的递归算法思想。我们总结一下，写出递归代码的关键在于，写出递推公式和找出终止条件。

也就是说我们需要：首先找到将大问题分解成小问题的规律，并基于此写出递推公式；然后找出终止条件，就是当找到最简单的问题时，如何写出答案；最终将递推公式和终止条件翻译成实际代码。

--------------------

## 四、建立递推关系 ##

对于一些不易用公式表达的问题，可以尽量发掘问题中的逻辑关系，用 **递推关系+终止条件** 的方式解决。

### 4.1 简单示例：反向打印字符串 ###

为了理解如何建立**递推关系**，我们先从一个简单的示例入手：

> 以相反的顺序打印字符串。

当然，你可以使用迭代的办法轻而易举地解决这个问题，即从字符串的最后一个字符开始遍历字符串。但是如何递归地解决它呢？

**递归算法思路：**

首先，我们可以将所需的函数定义为 printReverse(str\[0…n-1\])，其中 str\[0\] 表示字符串中的第一个字符。然后我们可以确定如下的递推关系，分两步完成给定的任务：

*  printReverse(str\[1…n-1\])：以相反的顺序打印子字符串 str\[1…n-1\] 。
 *  print(str\[0\])：打印字符串中的第一个字符。

请注意，我们在第一步中调用函数本身，根据定义，它使函数递归。下面给出代码：

#include<iostream>
    #include<stdio.h>
    using namespace std;
    
    // 递归函数 
    void printReverse(const char *str) 
    { 
      // 终止条件 
      if (!*str) 
        return;
      // 递归函数 
      printReverse(str + 1);
      // 打印首字符 
      putchar(*str);
    }
    
    int main()
    { 
    	// 初始化字符数组 
    	char s1[] = "Hello World!";
    	// 调用递归函数 
    	printReverse(s1);
    	return 0;
    }

运行结果：  
![在这里插入图片描述][2020100519433862.png_pic_center]  
以上就是**递推关系+终止条件**的递归算法思想。我们总结一下，对于一些不易用公式表达的问题，写出递归代码的关键在于，写出**递推关系**和找出**终止条件**。

### 4.2 简单示例：反转字符串 ###

为了更深一步理解递推算法，我们在上题的基础上，增大了难度。问题如下：

> 编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 char\[\] 的形式给出。不要给另外的数组分配额外的空间，你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。你可以假设数组中的所有字符都是 ASCII 码表中的可打印字符。

由于空间复杂度上的约束，因此要保证两个连续的递归调用之间没有额外的空间消耗。也就是说，我们应该把问题划分为独立的子问题。

因此，关于如何划分问题的一个想法是将每个步骤中的输入字符串减少为两个组件：

*  首字符和末尾字符。
 *  没有首字符和末尾字符的其余**子字符串**。

然后我们可以独立地解决这两个部分。根据上述思想，我们可以提出如下递推算法：

*  从输入字符串中获取首字符和尾随字符，即 str\[0\] and str\[n-1\]；
 *  就地交换首字符和末尾字符；
 *  递归调用函数来反转剩余的字符串，也就是 reverseString(str\[1…n-2\])。

给定输入字符串 “hello” ，下面演示如何分解并解决它：

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dqaW5qaWU_size_16_color_FFFFFF_t_70_pic_center 1]  
下面给出了上述算法的实现：

#include<iostream>
    #include<string>
    using namespace std;
    
    // 递归函数 
    void reverseString(int start, int end, string & s)
    { 
        if (start >= end) 
    	{ 
        	return ;
        } 
        // 首尾交换 
        char tmp = s[start];
        s[start] = s[end];
        s[end] = tmp;
        // 递归函数 
        reverseString(start + 1, end - 1, s);
    }
    
    int main()
    { 
    	string s1 = "Hello World!";
    	reverseString(0, s1.size(), s1);
    	cout<<"字符串反转后："<<s1<<endl;
    	
    	return 0;
    }

运行结果：  
![在这里插入图片描述][20201005215131544.png_pic_center]  
可以看出，每次递归调用只需要常量级的内存，以便交换前导和末尾字符。结果显而易见，它满足了问题的约束。

##  养成习惯，先赞后看！你的支持是我创作的最大动力！ ##

[AI]: https://blog.csdn.net/wjinjie
[AI _Github]: https://github.com/Keyird/DeepLearning-TensorFlow2.0
[04]: https://blog.csdn.net/wjinjie/article/details/106523294
[05]: https://blog.csdn.net/wjinjie/article/details/107356912
[06_ _ _ _ _ _ _]: https://blog.csdn.net/wjinjie/article/details/108151320
[07_ _ _]: https://blog.csdn.net/wjinjie/article/details/108360908
[08_ _]: https://blog.csdn.net/wjinjie/article/details/108363260
[09]: https://blog.csdn.net/wjinjie/article/details/108484738
[10]: https://blog.csdn.net/wjinjie/article/details/108773366
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dqaW5qaWU_size_16_color_FFFFFF_t_70_pic_center]: /images/20221123/f3fa232ae0d2424798eb321e57b227f5.png
[20201005225125983.jpg_pic_center]: /images/20221123/ce1eb8fdb5634c4180ffe6563f8009b3.png
[2020100519433862.png_pic_center]: /images/20221123/1cd67689cd3a44c5b987e1d4cf5d4091.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dqaW5qaWU_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221123/69d275e2f1ef4fac8f884d6805fbc68d.png
[20201005215131544.png_pic_center]: /images/20221123/6aedeae368eb498aaf61c6b0bdf83d19.png