递归、函数的调用机制及汉诺塔问题

递归

递归一个函数直接或间接调用自己的一种方法，它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解。递归要满足3个条件：一是递归必须得有一个明确的中止条件，要不然就很可能陷入死递归；二是递归函数所处理数据(或问题)的规模必须在递减，n个问题的解决依赖于n-1个问题的解决；三是这个转化必须是可解的。

函数的调用机制

当在一个函数的运行期间调用另一个函数时，在运行被调函数之前，系统需要完成三件事：
a).将所有的实际参数，返回地址(下一条语句的地址)等信息传递给被调函数保存；
b).为被调函数的局部变量(也包括形参)分配存储空间；
c).将控制权限转移到被调函数的入口；
从被调函数返回主调函数之前，系统也要完成三件事：
a>.保存被调函数的返回的结果；
b>.释放被调函数所占的存储空间；
c>.依照被调函数保存的返回地址将控制权限转移到调用函数。
当多个函数相互调用时，按照“后调用先返回”的原则，上述函数之间信息传递和控制权限转移必须借助

“栈”来实现，即系统将整个程序运行时所需的数据空间安排在一个栈中，每当调用一个函数时，就在栈

顶分配一块存储区，进行压栈操作；每当一个函数退出时，就释放它的存储区，进行出栈操作，当前运行

的函数永远都在栈顶位置！
在计算机看来，A函数调用A函数和A函数调用B函数本质上是一样的。每调用一个函数，进行压栈操作；每

当函数退出时，就释放它的存储区就行出栈操作，当前运行的函数永远都在栈顶位置。

循环和递归的比较

递归优点：易于理解(问题规模原来可以转化为范围越来越小的问题)

递归缺点：速度慢(由函数调用机制决定，每次递归都得调自己)，存储空间大(浪费空间很大)

循环优点：速度相对快 ，存储空间小(浪费空间很小)

循环缺点：不易理解(很多算法需要我们一个一个去推)

所有的循环都可以用递归实现，但所有的递归不一定可以用循环实现。

汉诺塔问题

问题描述：如何把A柱(第一根柱子)上面的n个盘子借助B柱(第二根柱子)移到C柱(第三根柱子)上？，且一次只能移动一个盘子，移动过程中小盘子必须始终放在大盘子上面(最下面的盘子编号最大)。

伪算法：1.当A柱子上只有1个盘子时，可直接将A柱上的盘子移到C柱

2.当A柱子上的盘子为n个时(n>1)，此时可利用递归的思想分3步解决：

1).将A柱上的n-1个盘子借助C柱移到B柱；

2).将A柱上的第n个盘子直接移到C柱上;

3).将B柱上的n-1个盘子借助A柱移到C柱上；

递归算法实现(规定柱子上至少有一个盘子)：

#include<stdio.h>
void Hanoitower(int n,char A,char B,char C)
{
	if(1==n)
	{
	     printf("将编号为%d的盘子从%c柱移到%c柱上\n",n,A,C);
	}
	else
	{
	     Hanoitower(n-1,A,C,B);
              printf("将编号为%d的盘子从%c柱移到%c柱上\n",n-1,A,C);  
	     Hanoitower(n-1,B,A,C);
	}
}
int main()
{
	int n;
	printf("请输入盘子的个数：");
	scanf("%d",&n);
         Hanoitower(n,'A','B','C');   
	return 0;
}

由盘子转移的次数可以推算出：汉诺塔的复杂度是2的n次方-1。

结束语

递归在很多地方用到，如树、图都是以递归的方式定义的。递归为我们解决复杂问题提供了方面(但这基本上是数学上的问题，所以理解要它的逻辑有时会很难)。学线性结构(数组、链表及其应用的栈、队列等)、递归及它们思想主要是为以后方面我们能将非线性问题转化为线性问题，进而通过线性结构的方法及思想来解决非线性结构问题。