数据结构 C 代码 递归

• 递归就是函数自身调用自身，即函数内部又使用到了该函数功能。递归的思想是把一个大型复杂问题层层转化为一个与原问题规模更小的问题，问题被拆解成子问题后，递归调用继续进行，直到子问题无需进一步递归就可以解决的地步为止。

1. 明确你这个函数想要干什么
2. 寻找递归结束条件
3. 找出函数的等价关系式

• 递归必须有结束条件，否则内存会溢出，
• 即使递归调用中有结束条件，但是如果递归的次数太多，也会发生内存溢出。

#include 


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


int clearAddTo(int paraN) {
	if (paraN <= 0) {
		return 0;
	} else {
		return clearAddTo(paraN - 1) + paraN;
	}// Of if
}// Of clearAddTo


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

	n = 5;
	sum = addTo(n);
    printf("rn0 adds to %d gets %d.rn", n, sum);

	n = 1;
	sum = addTo(n);
    printf("rn0 adds to %d gets %d.rn", n, sum);

	n = -1;
	sum = addTo(n);
    printf("rn0 adds to %d gets %d.rn", n, sum);


    printf("---- addToTest ends. ----rn");
}// Of addToTest


void main() {
	addToTest();
}// Of main

• 汉诺塔（Tower of Hanoi），又称河内塔，是一个源于印度古老传说的益智玩具。大梵天创造世界的时候做了三根金刚石柱子，在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘。大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定，在小圆盘上不能放大圆盘，在三根柱子之间一次只能移动一个圆盘。

#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 rn", paraSource, paraDestination);
		hanoi(paraN - 1, paraTransit, paraDestination, paraSource);
	}// Of if
}// Of hanoi


void hanoiTest() {
    printf("---- addToTest begins. ----rn");

	printf("2 platesrn");
	hanoi(2, 'A', 'B', 'C');

	printf("3 platesrn");
	hanoi(3, 'A', 'B', 'C');

    printf("---- addToTest ends. ----rn");
}// Of addToTest


void main() {
	hanoiTest();
}// Of main

• 算法的时间复杂度是 O(2^n) , 空间复杂度是 O(n)。