数据结构--2.3 栈与递归

• • 累加
  • 汉诺塔问题
  • • 算法说明
    • 代码实现
    • 时间复杂度与空间复杂度
  • 总结

累加可以用for循环，也可以用递归。代码如下：

#include 
#include 

int addTo(int n)
{
	if(n<=0)
	{
		return 0;
	}else
	{
		int num;
		num=addTo(n-1)+n;
		return num;
	}
}

int main()
{
	int num;
	num=addTo(5);
	printf("%d",num);
}

这个递归算法的时间复杂度是O（n），而for的时间复杂度却只有O（1），那我们为什么还要选择递归呢？因为递归有利于我们理解更复杂的问题，比如下面展示的经典的汉诺塔问题。

汉诺塔问题已经在不同课堂上反复听过很多遍了，这是一个十分经典的题：有A,B,C三根柱子，我们需要把A柱子上的n个圆盘挪到C柱子上。在挪动时有两个要求：
1.每次只能挪动一个盘子；2.小盘子只能放在大盘子上。
我们需要求挪动n个盘子，要挪动多少次。

那根据递归的思想，求挪动n个盘子的次数，我们只需要知道挪动（n-1）个盘子的次数，挪动（n-1）个盘子的次数，我们又只需要知道挪动（n-2）个盘子的次数，这样就可以形成一个递归的表达式。

我列出了三个盘子的挪动方式，如下图：

int hanoi(int n,char Source,char Target,char Assist)//Source代表圆盘柱，Assist代表辅助柱，Target代表目标柱
{
	if(n<=0)
	{
		return 0;
	}else
	{
		hanoi(n-1,Source,Assist,Target);
		printf("%c -> %crn",Source,Target);
		hanoi(n-1,Assist,Target,Source);
	}
} 

从这段代码我们可以看出来只需要三步将A柱子上n-1个盘子借助C柱子移到B上，将A最后一个盘子移到C上，最后将B柱子借助空A柱子移到C上。：

A -> B
A -> C
B -> C
A -> B
C -> A
C -> B
A -> B

汉诺塔问题的时间复杂度是O（2^n），
设盘子个数为n时，需要T（n)步，把A柱子n-1个盘子移到B柱子，需要T（n-1)步，A柱子最后一个盘子移到C柱子一步，B柱子上n-1个盘子移到C柱子上T（n-1)步，得递推公式T（n）=2T（n-1)+1，所以汉诺塔问题的时间复杂度为O(2^n)。
空间复杂度是O（n）。

递归的思想在解决简单的问题是会显得多此一举，但是在解决复杂问题时却可以将问题变得十分简洁，可以看出这是一种比较高级的算法思想。
递归的思想就是把复杂的问题转化为若干个与原问题相似但规模较小的问题。
递归算法有两个必要条件：
1.必须存在终止条件（即递归出口）；
2.过程的描述包含它本身，就是在过程或函数中调用自身。