数据结构 ---- 递归及应用（汉诺塔）

 对于递归来说，可以形象的形容为踢皮球行为，每次都踢给前一项，一直踢，踢到最后实在没得踢了，就只能实现了。所以对于递归来说，代码是特别的简单的，但是对逻辑的要求比较高，需要很强的逻辑思维，先从后往前踢，然后再从前往后去实现，以此来实现最终的代码。

虽说递归的应用不是很多，并且对于计算机内存的要求比较高，要求计算机一步步的计算保存数据，所以就很困难的实现，但是其实这也是另外一种逻辑思维，帮助我们更好的理解去使用C语言代码，去解决更多的问题。

其实，对于汉诺塔问题来说，没有那么多很深的逻辑可言，只有很简单的递归，就是先把（n-1）个盘子以目的地为辅助，辅助盘子为终点，而初始盘子依旧是初始盘子，然后将其移动到辅助盘子上，然后再把最下面的移过去，然后再依照这个道理继续进行下去，将复杂的问题简单化，这或许是递归带给我们的方便之处吧。

代码（基础应用）：

#include 


int addTo(int paraN) 
{
	int tempSum;
	printf("entering addTo(%d)\r\n", paraN);
	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 clearAddTo(int paraN) 
{
	if (paraN <= 0) 
	{
		return 0;
	} 
	else
	{
		return clearAddTo(paraN - 1) + paraN;
	}
}


void addToTest() {
	int n, sum;
    printf("---- addToTest begins. ----\r\n");

	n = 5;
	sum = addTo(n);
    printf("\r\n0 adds to %d gets %d.\r\n", n, sum);

	n = 1;
	sum = addTo(n);
    printf("\r\n0 adds to %d gets %d.\r\n", n, sum);

	n = -1;
	sum = addTo(n);
    printf("\r\n0 adds to %d gets %d.\r\n", n, sum);


    printf("---- addToTest ends. ----\r\n");
}

int main() 
{
	addToTest();
}

运行结果：

 代码（汉诺塔）：

#include 


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


void hanoiTest() {
    printf("---- addToTest begins. ----\r\n");

	printf("2 plates\r\n");
	hanoi(2, 'A', 'B', 'C');

	printf("3 plates\r\n");
	hanoi(3, 'A', 'B', 'C');

    printf("---- addToTest ends. ----\r\n");
}


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

测试结果：