C语言进阶指南（6）（函数递归详解）（内含汉诺比塔，青蛙跳台阶问题）

*欢迎来到博主的C语言进阶指南专栏

博主id:reverie_ly*

@toc

递归

在了解C语言递归程序之前，我想先请大家思考一个数学递归题：

已知f（n）=f（n-1）+1，f（0）=0。求f（6）的值

解法如下：f（6）=f（5）+1=（f（4）+1）+1，以此类推。

在数学中，递归是将一个未知项逐渐拆分为小项来计算出未知项的值。那么根据这种数学思想，递归程序的思路应该是：

将一个程序问题重复的拆分为子问题的集合，并将这些子问题的结果求出并汇总

以上例数学题为例，我们可以写出求解这个数学问题的程序。

int func(int n)
{
	if (n > 0) return func(n-1) + 1;//f（n）=f（n-1）+1
	if (n == 0) return 0;//f（0）=0
}

写出递归函数的要点如下：

1）清楚原项与子项的关系

2）知道底层项的结果

3）每次子项调用时都更加靠近底层项

4）函数内调用自身

以以递归的方式写出阶乘的函数为例，来深入一下递归的原理和作用。我们以上面的方法为参考，可以构思出来n！的通项为n*（n-1）!。0！为1.

于是我们可以写出计算阶乘的函数

int fac(int n)
{
	if (n > 0) return n * fac(n - 1);//n*（n-1）！
	if (n == 0) return 1;//0！=1
}

当函数被调用时，会在栈区申请一个空间，当函数执行结束或者返回函数值时，函数在栈区中的空间会被释放。

我们假设一个嵌套函数调用了四个函数的情况下，函数运行时在栈区上发生的情况如下：

我们回到递归求阶乘的那个例子，以4！为例。函数的运行情况在栈区上为：

我们可以发现函数调用时的特点是：先调用的后销毁，后调用的先销毁

我们可以利用这个顺序的特点来编写程序。例如我们编写一个程序，实现的效果是用户输入一个整数，屏幕上能按照顺序将每个数字一次打印：比如用户输入1234，屏幕上的打印结果为：1 2 3 4.。

如果我们使用前面介绍的循环语句%10，/10的办法来实现，我们得到结果将会是4 3 2 1.这是不符合我们想要的效果的。如果我们使用递归函数先调用的后输出的特点来写的话，就能够使用一个整数%10，/10的方法来顺序打印每个数字了。

void print(int n)
{
	if (n > 9)
		print(n / 10);
	printf("%d ", n % 10);
	return;
}

这个递归函数的原理如下：

递归导致的栈溢出

我们把函数的调用存放在栈区为进栈，函数运行结束在栈区中销毁称为出栈。我们上面已经知道了递归函数先进栈的后出栈的特点。那么如果我们在递归的过程中调用了太多函数的情况下，就会导致先前调用的函数无法出栈的结果，而此时函数的递归也仍未停止。栈区的空间是有限的，继续进栈就会导致栈溢出。

int main()
{
	main();
	return 0;
}

我们可以发现main（）函数会一直调用main（）函数，此时先前调用的main（）函数无法出栈，而函数的递归又未停止。就会导致栈溢出。

如果发生栈溢出的情况，编译器会爆出“Stack overflow”的警告

斐波那契数列

在数学中1 1 2 3 5 8 13 21 34 55……的数列被称为斐波那契数列，我们发现斐波那契数列的规律如下：除了第一个数字和第二个数字为1之外，其他数字都前两位数字之和。

我们前面已经讲了写出递归函数的方法就是找出原项和子项的逻辑关系，那么将斐波那契数列抽象为数学语言就是An=An-1+An-2。A1=A2=1。

我们利用这个逻辑关系可以写出斐波那契数列的递归函数

int fib(int n)
{
	if (n > 2) return fib(n - 1) + fib(n - 2);
	if（n==1||n==2） return 1;
}

fib（10）=55.

斐波那契数列也很好的体现了递归的缺点之一就是计算繁杂，如果我们尝试使用fib(50)，就会发现程序一直在运行，但是结果要很久才能输出（取决于计算机的算力）。

我们发现递归fib（50）需要调用2的50次方次函数才能得到返回值

青蛙跳台阶

青蛙跳台阶的问题如下：有一个青蛙，它一次能跳两个台阶，也可以跳一次台阶，那么当青蛙跳到第n个台阶时，总共有几种跳法。

当n=1时，青蛙有1种方法

当n=2时，青蛙可以先跳一阶，在跳一阶或直接跳两阶两种方法。

当n=3时，青蛙可以选择先跳一阶，在跳两阶，或先跳两阶在跳一阶的方式共3种

当n=4时，青蛙可以选择先跳一阶再用跳三阶的方法或先跳两阶再用跳两阶的方法共5种。

如果这么枚举下去，想要计算到n是很复杂的。我们假设青蛙离第n个台阶上还差一步，那么青蛙就有可能在第n-1的台阶或者n-2的台阶上。如果青蛙在n-1个台阶，青蛙就要有总共有跳（n-1）个台阶的方法，如果青蛙在n-2个台阶上，那么青蛙就总共有跳（n-2）个台阶的方法。所以青蛙跳上第n个台阶总共有跳（n-1个台阶）+（n-2个台阶）的方法

于是我们就又抽象出数学语言了，An=An-1+An-2。A1=1。.A2=2，这是一个很类似于斐波那契数列的问题，他们仅仅只是底层项不相等。..

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

测试结果：forg_jump(9)=55。

汉诺比塔问题

想让盘子在最低端由大到小排序，我们需要先将第n个的盘子挪到c柱上，那么我们需要先将前边的（n-1）个盘子按由大到小的规律挪到b柱，接着把第n个盘子挪到c柱，再将（n-1）个盘子挪到c柱完成排序。

由此可知，将n个盘子挪到c柱上所需要的步骤为（n-1）个盘子所需的步骤+1+（n-1）个盘子所需的步骤。

抽象出数学语言就是（n-1）*2+1.

int hanoi(int n)
{
	if (n == 0) return 0;
	if (n >= 1) return hanoi(n - 1) * 2 + 1;
}