用例子理解递归

想让APP和微信一样，可以流畅运行小程序？ | 体验即送大疆、华为、樱桃键盘！>>>

---

0.什么是递归

      在说什么是递归之前，我想正在阅读的你应该会使用循环来解决一些问题了。那循环又是什么呢？循环是指在程序中需要反复执行某个功能而设置的一种程序结构。它由循环体中的条件，判断继续执行某个功能还是退出循环。

      例如：1+2+3+4+……+10等于多少?（我们排除数学公式）

第一种解决方法就是可以使用循环来解决。

第二种解决方法就是使用递归来解决。

      可以看到，循环是反复执行某一段区域内的代码，直到符合终止条件，如果不加控制，就会形成死循环。而递归是函数体中调用自己，在使用递归的同时，一定要注意结束条件，如果不加控制，将无休止的调用自己，直到堆栈溢回出，因为函数每调用一次就会在栈上创建一个栈帧，函数调用结束后就会弹出该栈帧，而栈的大小不是无限的，所以递归调用次数过多的话就会导致栈溢出。而递归调用的特点是每递归一次，就要创建一个新的栈帧，而且还要保留之前的环境（栈帧），直到遇到结束条件。所以递归调用一定要明确好结束条件，不要出现死循环，而且要避免栈太深。。

      如果你去百度循环和递归的优缺点,可能有这样的答案：

递归算法：
优点：代码简洁、清晰，并且容易验证正确性。（如果你真的理解了算法的话，否则你更晕）
缺点：它的运行需要较多次数的函数调用，如果调用层数比较深，需要增加额外的堆栈处理，比如参数传递需要压栈等操作，会对执行效率有一定影响。但是，对于某些问题，如果不使用递归，那将是极端难看的代码。
循环算法：
优点：速度快，结构简单。
缺点：并不能解决所有的问题。有的问题适合使用递归而不是循环。如果使用循环并不困难的话，最好使用循环。

      我觉得这个优点和缺点是在大量接触循环和递归而总结出来的，对于我们这种小白，基本上不需要纠结的，我们也体会不到，所以暂且我们不去想这些，就像上面说的，如果你真的理解了算法的话，否则你更晕。

      我们接着来看，对于上面1+2+3+4+……+10等于多少这种简单的问题，循环和递归都可以解决，而用递归也没有显现出它的代码简洁，清晰。所以我觉得不能单一的将循环和递归做比较，就拿顺序结构，分支结构，循环结构，模块化结构，这四大结构来说，循环一直是作为一个基础内容，而递归是为了解决特定问题而出现的算法，本质上也属于循环的一种，对于上述问题，递归算法的优点非但没有显现出来，反而有点怀疑，所以解决一个问题时，要看这个问题的复杂程度，根据问题的复杂程度进而采取不同的算法，而不是说，我学了递归，我就应该使用它，因为书上说它的代码简洁。

然后想要运用递归，最重重重要的口诀，要记住：

• 明确这个递归函数的作用（不需要写出具体代码）
• 找到递归结束条件
• 找出函数的等价关系式或最小递归模型
• 不要试图跟踪递归过程

---

下面通过运用口诀来解决由易到难的几道题来理解递归：

1.斐波那数列

斐波那契数列指的是这样一个数列：

这个数列从第3项开始，每一项都等于前两项之和，这个也是在递归中常说的一道题。

第一步：
明确这个递归函数的作用，这个函数的作用是什么？就是输出第n项的值。

int fun(int n)
{
   
     

}

第二步：
找到递归结束条件，当n小于等于1或者2的时候，就应该结束递归。

int fun(int n)
{
   
     
	if(n<=2)
	{
   
     
		return 1;
	}
}

第三步：
寻找函数的等价关系式，上文中说明这个数列从第3项开始，每一项都等于前两项之和，也就是f(n)=f(n-1)+f(fn-2)。

int fun(int n)
{
   
     
	if(n<=2)
	{
   
     
		return 1;
	}
	return fun(n-1)+fun(n-2);
}

---

2.小青蛙上台阶

一只青蛙一次可以跳上1级台阶，也可以跳上2级，求该青蛙跳上一个n阶的台阶总共有多少种跳法。
第一步，确实递归函数作用，求n级的台阶有多少种跳法。
第二步，确实结束条件，当台阶等于0，1，2，分别有0，1，2种方法，我们可以将这个结束条件进行整理。

int fun(int n)
{
   
      
	if(n<=2)
	{
   
      
		return n;
	}
}

第三步，确定等价关系式 ，当有n阶台阶，选择跳1阶，就剩下fun(n-1)种方法，选择跳2阶，就剩下fun(n-2)种方法。两种方法加起来就是总数。

int fun(int n)
{
   
      
	if(n<=2)
	{
   
      
		return n;
	}
	return fun(n-1)+fun(n-2);
}

---

3.汉塔塔

      比较有名的就是汉诺塔（又称河内塔）问题，汉诺塔源于印度一个古老传说的益智玩具。大梵天创造世界的时候做了三根金刚石柱子，在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘。大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定，在小圆盘上不能放大圆盘，在三根柱子之间一次只能移动一个圆盘，还必须是最顶端的圆盘，这个题还是比较难的，我们来分析一下这个题。

A柱作为源，B柱作为辅助柱，C柱作为目标柱。
设N为盘数，当N等于1时，只需要一步：A——C 如下图：

设N为盘数，当N等于2时，需要三步：A——B，A——C，B——C 如下图：

设N为盘数，当N等于3时，需要7步：A——C，A——B，C——B，A——C，B——A，B——C，C——A如下图：

当N越来越大时，需要的步骤也越来越多，当N等于64，假如每秒钟正确移动一次，移完这些也需要5845.42亿年以上，而地球存在至今不过45亿年，这个数太大了！所以关于递归，大家千万不要跟踪大型递归的过程， 关键就是找出最小递归模型或者是上面所说的递归的等价关系式。

第一步，我们要在黑框框中显示消息，第几步哪个盘子从哪个柱子移动到了哪个柱子上。
这个打印函数需要4个参数和一个全局变量用于步数的输出。

void move(int id, char form, char to)
{
   
       
	cout << "第" << sum++ << "步：将" << id << "号盘子从" << form << "移动到" << to<<endl;
}

并且确定函数的目的：输出第几步哪个盘子从哪个柱子移动到了哪个柱子上，这个我们用move函数来输出。

第二步，找出递归结束条件，当n等于0时或者1（另一种写法，没有写出），作为结束条件。

第三步，就是最小递归模型的寻找。
我们有三个柱子和n个盘子，所以函数的定义应该是：void fun(int n, char a, char b, char c)，a,b,c分别对应三根柱子。我们寻找最小递归模型：fun(n)上一步fun(n-1)怎么走。当n等于1时，直接将盘子从A柱移到B柱即可，当n等于2时，如上图，需要三步，也是我们所寻找的最小递归模型，当n=2时
fun(n - 1, a, c, b);表示标记为为n-1盘，从A柱通过辅助柱C移动到B柱
move(n, a, c);表示标记为n的盘，从A柱移动到C柱
fun(n - 1, b, a, c);表示标记为为n-1盘，从B柱通过辅助柱A移动到C柱

将n-1看成一个整体，n和n-1就固定的三步，完整代码如下：

int sum=1;    //记录步数
void move(int id, char form, char to)
{
   
       
	cout << "第" << sum++ << "步：将" << id << "号盘子从" << form << "移动到" << to<<endl;
}
void fun(int n, char a, char b, char c)
{
   
       
	if (n == 0)return; 
	fun(n - 1, a, c, b);
	move(n, a, c);
	fun(n - 1, b, a, c);
}
int main(int argc, char** argv) {
   
       
	while (1)
	{
   
       
		sum = 0;
		int x;
		cin >> x;
		fun(x, 'A', 'B', 'C');
	}
	return 0;
}
}

例子就举到这里，慢慢学习，你会发现递归是一个很神奇的东西，我这样平平的一个人都可以理解，我觉得你们都可以理解，而学习递归还有一个不得不提的一个名词叫迭代，关于迭代，后面再说。

---