数据结构算法

递归（recursion）：程序调用自身的编程技巧。

  递归满足2个条件：

    1）有反复执行的过程（调用自身）

    2）有跳出反复执行过程的条件（递归出口）

 

递归例子：

（1）阶乘

         n! = n * (n-1) * (n-2) * ...* 1(n>0)

//阶乘int recursive(int i){	int sum = 0;	if (0 == i)		return (1);	else		sum = i * recursive(i-1);	return sum;}

（2）河内塔问题

//河内塔void hanoi(int n,int p1,int p2,int p3){	if(1==n)		cout<<"盘子从"<<p1<<"移到"<<p3<<endl;	else	{		hanoi(n-1,p1,p3,p2);		cout<<"盘子从"<<p1<<"移到"<<p3<<endl;		hanoi(n-1,p2,p1,p3);	}}

（3）全排列

  从n个不同元素中任取m（m≤n）个元素，按照一定的顺序排列起来，叫做从n个不同元素中取出m个元素的一个排列。当m=n时所有的排列情况叫全排列。

  如1,2,3三个元素的全排列为：

  1,2,3

  1,3,2

  2,1,3

  2,3,1

  3,1,2

  3,2,1 

//全排列inline void Swap(int &a,int &b){	int temp=a;	a=b;	b=temp;}void Perm(int list[],int k,int m){	if (k == m-1) 	{		for(int i=0;i<m;i++)		{			printf("%d",list[i]);		}		printf("n");	}	else	{		for(int i=k;i<m;i++)		{			Swap(list[k],list[i]); 			Perm(list,k+1,m);			Swap(list[k],list[i]); 		}	}}