数据结构07：栈与递归

摘要：递归是我们的老朋友了，无论是程序设计基础课程还是离散结构课程都讲到过它，但这一次学了栈之后再来体会系统是怎么处理我们的递归函数的。
一.代码块
1）累加的递归实现

实际上，递加或阶乘递归确实是我们接触的最简单的递归函数了，递归的本质就是一直访问要求函数的上一个函数值，例如要求addTo(3)，就访问到addTo(2)，用addTo(2)+3就请求到addTo(3)的值了，依此类推。

值得注意的是，我们在用递归的时候，一定要写好终止条件，不然递归函数会一直调用本身。

int addTo(int paraN)
{
	int tempSum;
	if(paraN <= 0)
	{
		printf("return 0\r\n");
		return 0;
	}
	else 
	{
		tempSum = addTo(paraN-1) + paraN;
		printf("return %d\r\n",tempSum);
		return tempSum;
	}
}

2）汉诺塔的递归

我这里的汉诺塔和老师的稍稍不一样，我的是从A到C，老师是从A到B。

我们重点要理解传入参数，第一个是圆盘数很好理解。第二个，第三个，第四个，分别是你当前要做的步骤的起始柱子，辅助柱子，终点柱子。

其实我们要求将n个圆盘从起点移到终点可以划分为3个步骤。第一部，将最上面的n-1个圆盘看做一个整体，将其从起点柱子借助终点柱子移到辅助柱子上面，然后将最下面的一个从起点移到终点，最后将n-1个圆盘，从辅助柱子借助起点柱子移到终点柱子上面来，整体就完成了。

具体代码如下。

int hanoi(int paraN,char paraSource,char paraTransit,char paraDestination)
{
	if(paraN <= 0)
	{
		return ;
	}
	else
	{
		hanoi(paraN-1,paraSource,paraDestination,paraTransit);
		printf("%c--->%c\n",paraSource,paraDestination);
		hanoi(paraN-1,paraTransit,paraSource,paraDestination);
	}
}

3）测试函数
这个由于比较简单，我就没有写测试函数了，放在main里面了
三.全部代码

#include 

int addTo(int paraN)
{
	int tempSum;
	if(paraN <= 0)
	{
		printf("return 0\r\n");
		return 0;
	}
	else 
	{
		tempSum = addTo(paraN-1) + paraN;
		printf("return %d\r\n",tempSum);
		return tempSum;
	}
}

int hanoi(int paraN,char paraSource,char paraTransit,char paraDestination)
{
	if(paraN <= 0)
	{
		return ;
	}
	else
	{
		hanoi(paraN-1,paraSource,paraDestination,paraTransit);
		printf("%c--->%c\n",paraSource,paraDestination);
		hanoi(paraN-1,paraTransit,paraSource,paraDestination);
	}
}

int main()
{
	printf("%d\n",addTo(5));
	
	hanoi(3,'A','B','C');
}

四.运行结果

return 0
return 1
return 3
return 6
return 10
return 15
15
A--->C
A--->B
C--->B
A--->C
B--->A
B--->C
A--->C

五.总结

说了这么多，栈在哪呢。其实编译器在运行代码的时候，系统就帮我们建立了栈了。

拿累加函数来举例：我们注意到，当我们要实现addTo(5)的时候，addTo(5)函数里面出现了addTo(4)要我们处理，处理了addTo(4)才能继续执行addTo(5)后面的内容，于是相当于一个更加紧急的任务addTo(4)出现了。

这时候系统就建立栈，先将相对不急的addTo(5)压栈放在了最下边等会处理，然后压栈addTo(4)放在上面，addTo(4)运行有需要处理addTo(3)，又先压addTo(4)，再压addTo(3)…以此类推，直到addTo(0)，函数有了返回值，再依次的出栈，解决addTo(1)，addTo(2)…addTo(5)，这就是系统处理你的递归函数方式，用到了栈。如下图：