漫谈递归转非递归

本文首发于我的公众号 Linux云计算网络（id: cloud_dev） ，专注于干货分享，号内有 10T 书籍和视频资源，后台回复 「1024」 即可领取，欢迎大家关注，二维码文末可以扫。

一：递归的思想

      之前面试腾讯，面试官问了一个问题：说说递归和循环的区别？当时没有答出问题的本质，只是简单地解释了这两个词的意思，囧，今天就借由这篇文章来谈谈自己对递归的理解。

      我们一般对递归的印象就是一个函数反复的“自己调用自己”，代码精炼，便于阅读。但是，从本质上来说，递归并不是简单的自己调用自己，而是一种分析和解决问题的方法和思想。简单来说，递归思想就是：把问题分解成规模更小，但和原问题有着相同解法的问题。典型的问题有汉诺塔问题，斐波那契数列，二分查找问题，快速排序问题等。PS：其实像我们常见的分治法和动态规划法都是递归思想的经典应用。

      既然的递归的思想是把问题分解成规模更小但和原问题有着相同解法的问题，那是不是所有具有这样特性的问题都能用递归来解决呢？答案是否定的。除了这个特性，能用递归解决的问题还必须具有一个特性：存在一种简单情境，能让递归在简单情境下退出，也就是要有一个递归出口。总结一下就是，能用递归解决的问题，必须满足以下两个条件：

       比如，阶乘问题：fact(n) = n*fact(n-1)，当n = 1时，存在简单情境：fact(1) = 1。斐波那契数列问题：fib(n) = fib(n-1) + fib(n-2)，当n = 1和n = 2时，存在简单情境：fib(1) = 1, fib(2) = 1。上述两个问题仅存在一种简单情境，有些问题可能存在两种以上的简单情境（在写代码时务必都要考虑到），比如：二分查找问题：第一种简单情境是需要查找的元素与中值元素相等；第二种简单情境是：待查找的元素没在序列中，则通过比较待查找元素和最后一个划分的元素来确定结果。

      再说一个例子，判断一个序列是否是回文串（形如“level”, "abba"这样的字符串），这个问题也可以分解成解相同的子问题（去掉首尾的字符），仔细分析可以看出，同样也存在两种递归的简单情境，分别为当字符个数为奇数和偶数的情况下，当n=even时，简单情境为空字符串，空字符串也是回文串，当n=odd，简单情境为只有一个字符，同样也为回文串。

 二：递归的效率

      递归导致一个函数反复调用自己，我们知道函数调用是通过一个工作栈来实现的，在大多数机器上，每次调用函数时大致要做三个工作：调用前先保存寄存器，并在返回时恢复；复制实参；程序必须转向一个新位置执行。其中，具体要保存的内容包括：局部变量、形参、调用函数地址、返回值。那么，如果递归调用N次，就要分配N*局部变量、N*形参、N*调用函数地址、N*返回值。这势必是影响效率的。在C++中，inline函数就是为了改善函数调用所带来的效率问题而做的一种优化。递归就是利用系统的堆栈保存函数当中的局部变量来解决问题的，说白了就是利用堆栈上的一堆指针指向内存中的对象，并且这些对象一直不被释放，直到遇到简单情境时才一一出栈释放，所以总的开销就很大。栈空间都是有限的，如果没有设置好出口，或者调用层级太多，有可能导致栈空间不够，而出现栈溢出的问题。为了防止无穷递归现象，有些语言是规定栈的长度的，比如python语言规定堆栈的长度不能超过1000。还有就是当规模很大的时候，尽量不使用递归，而改为非递归的形式，或者优化成尾递归的形式（后面讲）。

      与递归相关联的有几个词，分别是循环，迭代和遍历。咋一看，都有重复的意思，但有的好像又不只是重复，具体它们之间有什么区别呢？我的理解是这样的：

      递归由于效率低的问题，经常要求转换成循环结构的非递归形式。

 三：递归转尾递归

      有些简单的递归问题，可以不借助堆栈结构而改成循环的非递归问题。这里说的简单，是指可以通过一个简单的数学公式来进行推导，如阶乘问题和斐波那契数列数列问题。这些可以转换成循环结构的递归问题，一般都可以优化成尾递归的形式。很多编译器都能够将尾递归的形式优化成循环的形式。那什么是尾递归呢？

      我们先讨论一个概念：尾调用。顾名思义，一个函数的调用返回都集中在尾部，单个函数调用就是最简单的尾调用。如果两个函数调用：函数A调用函数B，当函数B返回时，函数A也返回了。同理，多个函数也是同样的情况。这就相当于执行完函数B后，函数A也执行完了，从数据结构上看，在执行函数B时，函数A的堆栈已经大部分被函数B修改或替换了，所以，栈空间没有递增或者说递增的程度没有普通递归那么大。这样在效率上就大大降低了。

      尾递归就是基于尾调用形式的递归，只不过上述的函数B就是函数A本身。可见，尾递归其实是将普通递归转换成一种迭代的形式，下一层递归所用的栈帧可以与上一层有重叠，局部变量可重复利用，不需要额外消耗栈空间，也没有push和pop。 这样就大大减少了递归调用栈的开销。下面举两个简单的例子，看看怎么将递归转换成尾递归？

1、阶乘函数：fact(n) = n*fact(n-1)

      前面说过，尾递归其实是具有迭代特性的递归，时间复杂度为O(n)。我们可以抓住这个特点进行转化，既然是迭代形式，那么一定要有迭代的统计步数。我们记录当统计步数到达临界条件时，就退出（临界条件可以有两种，一种是递增到n；一种是递减到简单情境）。所以，对应就有两种转化思路：

思路一：统计步数从简单情境递增到n。

用5！来举例子：

思路二：统计步数从n递减到简单情境。

2、斐波那契数列：fib(n) = fib(n-1) + fib(n-2)      同阶乘函数，该问题也有两种转化思路。

思路一：统计步数从简单情境递增到n。

 引申：这个地方跟前面的主题没有直接关系，属于斐波那契数列的引申问题。在斐波那契数列中，如果兔子永远不死，一直繁衍下去，则怎么解？很明显，这是个大数问题，有兴趣的同学可以尝试去写写代码，下面贴上我自己写的。