数据结构学习笔记：递归和汉诺塔问题

什么是递归

在数据结构—树中，对于树的遍历采用的是递归来遍历的。
递归就好比套娃，在满足条件的情况下会一直调用本身。问题的求解过程就是划分成许多相同性质的子问题的求解，而小问题的求解过程可以很容易的求出，这些子问题的解就构成里原问题的解了。

流程图

递归的优缺点

递归使程序优雅。但是，如果性能至关重要，请使用循环代替，因为递归通常要慢得多。

实例：使用递归函数计算一个给定的数的阶乘：

#include 
 
double factorial(unsigned int i)
{
   if(i <= 1)
   {
      return 1;
   }
   return i * factorial(i - 1);
}
int  main()
{
    int i = 15;
    printf("%d 的阶乘为 %fn", i, factorial(i));
    return 0;
}

 

 汉诺塔问题

汉诺塔（Tower of Hanoi）是根据一个传说形成的数学问题：

最早发明这个问题的人是法国数学家爱德华·卢卡斯。

传说越南河内某间寺院有三根银棒，上串 64 个金盘。寺院里的僧侣依照一个古老的预言，以上述规则移动这些盘子；预言说当这些盘子移动完毕，世界就会灭亡。这个传说叫做梵天寺之塔问题（Tower of Brahma puzzle）。但不知道是卢卡斯自创的这个传说，还是他受他人启发。

若传说属实，僧侣们需要2的64次方-1 步才能完成这个任务；若他们每秒可完成一个盘子的移动，就需要 5849 亿年才能完成。整个宇宙现在也不过 137 亿年。

这个传说有若干变体：寺院换成修道院、僧侣换成修士等等。寺院的地点众说纷纭，其中一说是位于越南的河内，所以被命名为“河内塔”。另外亦有“金盘是创世时所造”、“僧侣们每天移动一盘”之类的背景设定。

算法求解

解法的基本思想是递归。假设有 A、B、C 三个塔，A 塔有 N 块盘，目标是把这些盘全部移到 C 塔。那么先把 A 塔顶部的 N-1 块盘移动到 B 塔，再把 A 塔剩下的大盘移到 C，最后把 B 塔的 N-1 块盘移到 C。

#include 
using namespace std;

void Towers(int n,char a,char b,char c){
	if(n==1){
		cout<<"Move disk "<n;
	Towers(n,'A','B','C');
	cout<< endl;
	
	
}

运行结果 

 2011年电影《猿族崛起》曾出现汉诺塔以测试猩猩的智商。其后续电影《猿族崛起2》中也有类似的场景。

难怪老师说汉诺塔问题是智商的分界线。由于在课堂上未能回答两个盘子需要移动几次，说明至少在那时我的智商是不如猩猩的。。。。。。