递归定义
递归定义是一种直接或者间接引用自身的定义方法。
递归包括两部分：
基础部分（直接形式列举）
递归部分（给出方法）
如 斐波那契数列的递归定义
{ f0 = 0, f1 = 1
{f(n) = f(n-1)+f(n-2) n>1
递归算法
使用递归定义的算法
如
long Fib(long n) { if(n<=1) return n; else return (Fib(n-2) +Fib(n-1)); }
递归的优点是简洁。缺点是耗时长(尤其是在递归次数多的时候）。
（使用如下代码可以得到运行时间）
#include<ctime> clock_t start_t, end_t; start_t = clock(); ............. end_t = clock(); std::cout << "Spend " << (double)(end_t - start_t)/1000.0 << " s\n";
其他的一些递归例子：
问题1 ：逆序输出正整数的各位数
设有正整数n = 12345,
输出各位数的逆序形式（54321）。
分析（使用递归）：
1. 首先输出末位数
2. 然后输出剩下的逆序形式
c++实现：
void print_digit(unsigned n) { std::cout << n%10; //1.输出末位数，使用求余（%）， if (n >= 10) //递归条件，非常重要，是递归停止的条件。 print_digit(n / 10); //2. 输出剩下的数的逆序形式，使用/ 得到剩下的。 }
问题2： 汉诺塔问题
假设有3个塔座：x,y,z.
塔座x上有从小到大编号为1，2，...n的n个圆盘，
要求把x的圆盘全部搬到z上，且：1.每次只能移动一个圆盘。2.大的盘子不能放在小的盘子上。
分析：
1.把第n个盘子移动到z上（先把n-1个盘子移动到y上）
2.把剩下的（n-1）盘子移动到z上
c++实现：
#include<iostream> int count = 0; //将第n个塔从a移动到b void move_tower(int n, char a, char b) { std::cout << n << ": "<<char(a) << "->" << char(b); std::cout<< "\n"; count++; } //移动n个塔，从x移动倒z，以y为中间点 void hanio(int n, char x, char z, char y) { if (n) { hanio(n - 1, x, y, z); move_tower(n, x, z); hanio(n - 1, y, z, x); } } int main() { int active = 1; while (active) { count = 0; std::cout << "输入塔的层数: "; int n; std::cin >> n; if (n < 1) { std::cout<<"无效输入，即将退出\n"; break; } hanio(n , 'x', 'z', 'y'); std::cout << "用了" << count << "次\n"; } system("pause"); return 0;
问题3： 排列组合问题。
问题，设有n个自然数的集合，输出集合产生的各种排列（有序）。
如集合{0,1,2}的排列有
0,1,2; 0,2,1;
1,0,2; 1,2,0;
2,0,1; 2,1,0;
问题分析：可以分为两步
1.确定排列的开头
2.排剩下的集合
c++实现：
#include<iostream> void perm(int a[], int k, int n) { if (k == n-1) //当k=n-1时，即已经排列完了，进行输出。 { for (int i = 0;i < n; i++) std::cout << a[i] << " "; std::cout << "\n"; } else { for (int i = k; i < n; i++) { int t = a[k]; a[k] = a[i]; a[i] = t; //排第k位 perm(a, k+1, n); //剩下的 从(k+1)开始排 t = a[k]; a[k] = a[i]; a[i] = t; //还原 } } }
int main() { int a[10] = { 0,1,2,3,4,5,6,7,8,9 }; perm(a, 0, 6); system("pause"); return 0; }
