算法递归讲解

🎈 作者：Linux猿

🎈 简介：CSDN博客专家🏆，华为云享专家🏆，Linux、C/C++、面试、刷题、算法尽管咨询我，关注我，有问题私聊！

🎈 欢迎小伙伴们点赞👍、收藏⭐、留言💬

各位考研小伙伴们晚上好呀！今天我们来学习下递归。在许多考研算法中都会使用到递归的思想来解决问题，递归是学习许多算法的基础，接下来就让我们学习下递归吧！

程序调用自身的编程技巧称为递归，一个程序不断的调用自身，直到满足一定条件才停止，可以用流程图表示如下：

上面只是一个大致的处理流程，具体实现流程的模块不一定要和上面的完全一致。比如：在调用递归函数后，可能先处理下数据，然后再判断是否结束，需要灵活运用。

大家应该都对斐波那契数列有所了解，在数学/数据结构/算法中都会有所涉及。斐波那契数列通常是如下的数列：

 0，1,1，2,3，5，8，13……

可以用公式表示为：

f[0] = 0;

     f[1] = 1;

     f[i] = f[i-1] + f[i-2]（i >= 2）;

用代码表示为：

int fibonacci(int n){    if (n == 0 || n == 1) {        return 1;    }    return fibonacci(n - 1) + fibonacci(n - 2);}

上述代码中，fibonacci便是一个递归调用的函数，其中，结束递归的条件为：

if (n == 0 || n == 1) {    return 1;}

例如：求解f[5]，调用过程如下

从上图中可以看到，每次求解中都是再调用fibonacci函数，直到遇到结束条件。

假设有一个迷宫，迷宫中的空白格为可以走的位置，X的方格表示不能走，S代表起点，E代表终点，求解从起点是否能到达终点，迷宫如下图所示：

  迷宫求解需要搜索算法来解决，如果用到深度优先搜索算法求解迷宫，实质上是一个不断递归的过程。

代码实现如下：

int mazeSolution(int step, int x, int y){    ……    if (str[x][y] == 'E') {        return step;    }    ……    int newStep = mazeSolution（step+1, sx, sy）;    ……    return newStep;}

在上述代码中，搜索的终止条件为找到终点E，当然搜索过程中需要判断是否出界以及判断当前格子是否可以进入。

递归一定要注意递归的终止条件，不然会成为无限递归！递归通常是服务于其它的数据结构，比如：深度优先搜索算法、快速排序、归并排序等，需要理解其原理才能熟练运用，大家有不理解的可以在评论区留言哦！

CSDN博客专家🏆，华为云享专家🏆，Linux、C/C++、面试、刷题、算法尽管咨询我，关注我，有问题私聊！

 欢迎小伙伴们点赞👍、收藏⭐、留言💬