验证递归，可以用数学归纳法：当n=0, 1的时候, 结果正确.假设函数对于n-1是正确的, 那么函数对n结果也正确.如果这两点是成立的，我们知道这个函数对于所有可能的n都是正确的。如何找到递归算法：你必须要示范如何解决问题的一般情况, 通过将问题切分成有限小并更小的子问题，假设n-1成立，那么n需要怎么表示？你必须要示范如何通过有限的步骤, 来解决最小的问题(基本用例)，即0或者1如果这两件事完成了, 那问题就解决了. 因为递归每次都将问题变得更小, 而一个有限的问题终究会被解决的, 而最小的问题仅需几个有限的步骤就能解决.递归的例子：e.g.1 斐波那契数列递归法，然而这种解法效率不高！非递归法：------------------------------------------------------------------------------------e.g.2阶乘递归法：long factoria(int n){return n <= 0 ? 1 : factoria(n - 1)*n;}-------------------------------------------------------------------------------------e.g.3汉诺塔有三根杆子A，B，C。A杆上有N个(N>1)穿孔圆盘，盘的尺寸由下到上依次变小。要求按下列规则将所有圆盘移至C杆：1.每次只能移动一个圆盘.2.大盘不能叠在小盘上面.递归法：显示步骤：void hanoi(int n, char A, char B, char C){if (n == 1)cout << A << "-->" << C << endl;else{hanoi(n - 1, A, C, B);cout << A << "-->" << C << endl;hanoi(n - 1, B, A, C);}}总共需要移动多少次盘子：int count(int n){int c = 0;if (n == 1)c = n;elsec = 2 * count(n - 1) + 1;return c;}----------------------------------------------------------------------------------
