数据结构第六天——累加的递归，汉诺塔

一、累加的递归

核心代码

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

总代码

#include
#include

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

void addToTest() {
	int n, sum;
	printf("---- addToTest begins. ----\n");
	
	n = 5;
	sum = addTo(n);
	printf("\n0 adds to %d gets %d.\n", n, sum);
	
	n = 1;
	sum = addTo(n);
	printf("\n0 adds to %d gets %d.\n", n, sum);
	
	n = -1;
	sum = addTo(n);
	printf("\n0 adds to %d gets %d.\n", n, sum);
}
int main() {
	addToTest();
	
	return 0;
}

运行结果

二、汉诺塔

 核心代码

void 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);
	}
}

总代码

#include

void 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() {
	int N;
	printf("请输入想移动的盘子数：");
	scanf("%d", &N);
	
	char Source, Transit, Destination;
	Source = 'A';
	Transit = 'B';
	Destination = 'C'; 
	hanoi(N, Source, Transit, Destination);
	
	return 0;
}

运行结果

 

 总结

1.递归函数，我的理解是，就是在使用时，自己调用自己

2.感觉递归函数的优点就是可读性很好，容易理解，但是时间和空间消耗比较大，甚至可能发生栈溢出的问题

3.递归的函数在我看来，就是把第一种情况单独说明，其它的情况都是一个类型，比如累加，将0和其它情况分成两类，汉诺塔也是一样的

4.汉诺塔的难点在于你输入的名字和在递归中调用的不一样，需要理解一下，看清楚位置和每个位置的意义