数据结构我好爱：栈的应用 --递归

递归的实现就是通过了计算机内部的栈才得以实现。

        递归累加与汉诺塔！

递归需要终止条件来结束迭代：通常情况表现为边界条件。

递归加法：

int add_recursion(int n) {
	if (n == 1) return 1;
	return add_recursion(n - 1) + n;
}

完整代码：

#include
int add_recursion(int n) {
	if (n == 1) return 1;
	return add_recursion(n - 1) + n;
}

int add(int n) {
	int sum = 0;
	for (int i = 0; i <= n; i++) {
		sum += i;
	}
	return sum;
}

void Test() {
	printf("add = %dn", add(5));
	printf("add_recursion = %d", add_recursion(5));
}

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

汉诺塔：“汉诺塔是智商的分界线！”

汉诺塔的步骤：A-> 经过B

1.把A上方n-1个放上B

2.移动最下方A->C

3.把B上的n-1个全放在C上

void hanoi(int n, char source, char dest, char M) {
	if (n == 0) return;
	else {
		hanoi(n - 1, source, M, dest);
		printf("%c-->%cn", source, dest);
		hanoi(n - 1, M, dest, source);
	}
}

 值得注意的是汉诺塔的时间空间复杂度：

时间： 

空间：:栈空间可以重复利用

 完整代码：

#include

void hanoi(int n, char source, char dest, char M) {
	if (n == 0) return;
	else {
		hanoi(n - 1, source, M, dest);
		printf("%c-->%cn", source, dest);
		hanoi(n - 1, M, dest, source);
	}
}
//----------------------------------------------
int add_recursion(int n) {
	if (n == 1) return 1;
	return add_recursion(n - 1) + n;
}

int add(int n) {
	int sum = 0;
	for (int i = 0; i <= n; i++) {
		sum += i;
	}
	return sum;
}
//---------------------------------------------
void Test() {
	printf("add = %dn", add(5));
	printf("add_recursion = %d", add_recursion(5));
}

void Test1() {
	hanoi(3, 'a', 'b', 'c');
}

int main() {
    Test();
	Test1();
	return 0;
}