“通俗易懂的文字”＋“经典案例”让你顺利入门“递归算法”

(大佬请绕行，比较基础!) 递归是非常常见的一种算法，非常经典，可以解决非常多的问题。但我估计虽然大部分人知道递归，也能看得懂递归，但在实际运用中，很容易被递归给搞晕（数据，变量，函数等来回的出栈入栈）。今天写篇文章分享下，或许，能够给你带来一些帮助。

01 什么是递归

递归是一种解决问题的方法，将问题分解成规模更小的问题，不断地调用自身，解决小问题，直至问题不可再分，递归一般都是从结束条件一步一步往回计算

02 递归三定律

1) 递归必须有一个可以结束的条件，不然会陷入无限递归的噩梦中。而且，我们必须能根据当前参数的值，能够直接知道函数的返回结果是什么

2) 递归算法必须能改变状态向基本结束条件演进（必须能够有个最小规模的情况最为结束条件）

3) 递归算法必须调用自身

03 递归调用的原理

当一个函数被调用的时候，系统会把调用时的现场数据押入到系统调用栈（某段内存空间）

1)现场数据就是指函数变量名，函数所包含的参数，局部变量等

2) 每次调用，压入栈的现场数据称为栈帧

3) 当函数返回时，从调用栈的栈顶取得返回地址，恢复现场，弹出栈桢，按内存地址返回

一般来讲，系统调用栈容量有限，当递归的层数太多，超过递归最大层数，会报错，目前python支持最高1000层的调用

查看python的最大递归层数

其实递归的理解从语言上讲，基本上就这么多。下面开始分析一些代码实现

04 斐波那契数列

该数列由0和1开始，后面的每一项数字都是前面两项数字的和，数列的规律呈现为这个样子：[0,1,1,2,3,5,8,13,21···]，我们根据上述的递归三大定律分析来看：

1) 首先确认递归结束的条件，那么就是0，1，2这三个值，是定死的值

2) 对于大于2的索引值，有如下规律，f(n) = f(n - 1) + f(n - 2)，于是就可以构造如下递归函数求得计算结果

3) 因为要保存每一次的计算结果，最后累加，所以要有return值，将每一次递归的结果记录

代码实现如下

05 进制转换

将十进制数转换为2/8/16进制的字符串形式

1) 递归的结束条件为：当前数值小于要转换的进制大小了

2) 比如说转换为2进制，那么就始终除以2取余数，那么就可以利用递归的算法拿到每次的结果，将问题规模一次次的减小

代码如下

06 字符串反转

要做这么个事情：“abcdefg” ->“gfedcba”（当然有很多方法，这里主要讲递归实现）

1) 递归结束条件为：原字符串只剩下最后一个的时候，这时候就不需要反转了

2) 每次收集当前字符串的s[0]的字符作为反转，减小问题规模

代码如下

07 总结

本文主要分享了递归相关的概念和理解，并提供了几个最最基础的利用递归思想解决问题的代码(可能你会觉得本篇中的代码很简单，主要是不想给刚接触递归的那些人弄昏)，下一篇会分享几个稍微复杂一点点的案例(但整体还是递归问题中比较简单的那种)。我觉得，最开始接触递归，懵逼是正常的，只有不断的练习，不断的思考，才有可能用好这种牛逼的方法。

我是一名奋战在编程界的pythoner，工作中既要和数据打交道，也要和erp系统，web网站保持友好的沟通……时不时的会分享一些提高效率的编程小技巧，在实际应用中遇到的问题以及解决方案，或者源码的阅读等等，欢迎大家一起来讨论！如果觉得写得还不错，欢迎关注点赞，谢谢。