什么是递归？

递归（英语：Recursion），⼜译为递回，在数学与计算机科学中，是指在函数的定义中使⽤函数⾃⾝的⽅法。递归⼀词还较常⽤于描述以⾃相似⽅法重复事物的过程。例如，当两⾯镜⼦相互之间近似平⾏时，镜中嵌套的图像是以⽆限递归的形式出现的。也可以理解为⾃我复制的过程。

——维基百科

~~这就是递龟~~

让我们看一下Google的回答：

你也一定熟悉这个故事：

通俗来讲，递归就是不停重复一件事物本身的某个阶段，就像包子馅的包子，他的极限实际上是一个馒头。

放到程序里来讲，递归就是一个函数不停地调用自身的一个过程。

我们可以借用斐波那契数列来了解这一过程：

下面，我们来尝试用递归的方法来用代码实现斐波那契数列（求取前46项）：

#include<stdio.h>

int Fibonacci(int n)
{
	if(n==0)
		return 0;
	else if(n==1)
		return 1;
	else 
		return Fibonacci(n-1)+Fibonacci(n-2);
}

int main()
{
	int n;
	scanf("%d",&n);
	printf("%d\n",Fibonacci(n));
	return 0;
}

整个代码只需要一个

return Fibonacci(n-1)+Fibonacci(n-2);

就能自己把结果算出来，是不是很神奇？

这就是前面说的，自己调用自己。在n不断递减的过程中，最终达到边界1或0，得到返回值后再将值往前依次传递，得到最初的斐波那契数值。

这⾥使⽤递归⽅法求斐波那契数列的第项只是为了帮助理解递归，使⽤递归求斐波那契数列并不是⼀个好的⽅法（⼗分耗时，并且占用较多内存），更常⽤的⽅式是直接递推。

int Fibonacci[30];
Fibonacci[0] = 0;
Fibonacci[1] = 1;
for (int i=2; i<30; i++) 
{
    Fibonacci[i] = Fibonacci[i-1] + Fibonacci[i-2];
}

至于递归为什么会更加耗时，可以参考下图：

从图中可以看到，递归的过程中产生了许多重复项，比如F(2),F(3)等，都计算了不止一次，这就大大影响了程序的运行效率。因此，在做题中，我们要根据实际情况来使用最合适方法，至于为什么递归更加复杂还要使用，我们稍后再讲。（事实上，递归方便了程序员，为难了电脑）

再试着用递归来求取最大公约数(GCD)，

传统的最大公约数计算方法比较常用的是辗转相除法，那么我们用正常循环写出来就是：

#include<stdio.h>

int main()
{
	int a,b;
	scanf("%d%d",&a,&b);
	while(b!=0)
	{
		int tmp=b;
		b=a%b;
		a=tmp;
	}
	printf("%d\n",a);
	return 0;
}

而用递归写出来就是：

#include<stdio.h>

int gcd(int x,int y)
{
	if(x%y==0)
		return y;
	else
		return gcd(y,x%y);
}

int main()
{
	int a,b;
	scanf("%d%d",&a,&b);
	printf("%d\n",gcd(a,b));
	return 0;
}

甚至可以写的更简洁一点：

int gcd(int x,int y)
{
    return y==0?x:gcd(y,x%y);
}

对比上面的两种方法，递归和循环的优缺点十分明显：

递归算法：

优点：代码简洁、清晰，并且容易验证正确性。

缺点：

1、它的运行需要较多次数的函数调用，如果调用层数比较深，每次都要创建新的变量，需要增加额外的堆栈处理，会对执行效率有一定影响，占用过多的内存资源。

2、递归算法解题的运行效率较低。在递归调用的过程中系统为每一层的返回点、局部变量等开辟了栈来储存。递归次数过多容易造成栈溢出等

循环算法：

优点：速度快，结构简单。

缺点：并不能解决所有的问题。有的问题适合使用递归而不是循环。如果使用循环并不困难的话，最好使用循环

事实上，递归是另一种循环，所有能用循环写的函数都能用递归写出来，但递归能写的循环却不一定做得到；

例如，著名的汉诺塔问题：

汉诺塔（Hanoi Tower），又称河内塔，源于印度一个古老传说。大梵天创造世界的时候做了三根金刚石柱子，在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘。大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定，任何时候，在小圆盘上都不能放大圆盘，且在三根柱子之间一次只能移动一个圆盘。问应该如何操作？

简单来讲就是要把n个盘子从A柱子上移到C柱子上，盘子大小顺序不能颠倒，求操作步骤？

参考一下动图演示：

只有三个盘子时，可以很容易发现汉诺塔的规律，先把A柱上除最后一个大圆盘之外的小圆盘移到同一根柱子上，最后把最大的圆盘移到C柱，再把剩下的小圆盘如法炮制移到C柱上，完成转移。

而其中的重复步骤，递归方法可以帮我们轻松实现：

#include<stdio.h>

void hanoi(int n,char a,char b,char c)
{
	if(n==1) 
		printf("%c -> %c\n",a,c);       /*如果只有一个圆盘，则直接从a柱子移动到c柱子*/
	else
	{
		hanoi(n-1,a,c,b);		/*将a柱子n-1个圆盘移动到b柱子*/
		printf("%c -> %c\n",a,c); 	/*将a柱子n-1个圆盘移动到b柱子*/
		hanoi(n-1,b,a,c);		/*再把b上暂时放着的n-1个圆盘移动到c*/
	}
}

int main()
{
	int n;
	scanf("%d",&n);
	hanoi(n,'a','b','c');
	return 0;
}

代码不要求大家一次就能理解，可以课下慢慢看。这里只是向大家展示一下递归这种算法的强大与清晰的逻辑关系，大家以后做题的时候就可以考虑使用递归去解决了。

第一次讲课——递归

什么是递归？

Thanks for Watch！