递归算法及经典递归例子C++代码实现【全排列，阶乘，裴波那契数列等】

参考博客：https://www.cnblogs.com/xiaoliu66007/p/3927111.html
https://blog.****.net/MsStrbig/article/details/79823555

递归（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
算法思想：求n位的字符串的全排列，先确定第0位，然后对后面n-1位进行全排列，在对n-1为进行全排列时，先确定第1位，然后对后面的n-2位进行全排列…由此得到递归函数和递归的结束条件。全排列也就是交换位置，到n-2位时，就是将n-2和n-1交换位置。

例子：abc，第一位是a固定，对后面的bc交换位置得abc,acb.
当a和b交换位置之后，得到bac，对ac进行全排列bac,bca.
当a和c交换位置之后，得到cba，对ba进行全排列得cba,cab.

#include<iostream>
using namespace std;
//交换
void swap(int &a , int &b)
{
	int temp;
	temp = a;
	a = b;
	b = temp;
 } 
 //全排列递归算法
void Perm(int list[] , int k ,int m) 
{
	//list 数组存放排列的数，K表示层 代表第几个数，m表示数组的长度
	if(k==m)
	{
		//K==m 表示到达最后一个数，不能再交换，最终的排列的数需要输出；
		for(int i=0 ;i<=m ;i++)
		 cout<<list[i];
		 cout<<endl; 
	 } 
	 else{
	 	for(int i=k;i<=m;i++)
	 	{
	 		swap(list[i],list[k]);
	 		Perm(list,k+1,m);
	 		swap(list[i] , list[k]);
		 }
	 }
	 
}
int main(void)
{
   int a[]={1,2,3};
   int m=2;
   Perm(a,0,2);
	/* 显示结果
  123
  132
  213
  231
  321
  312
*/
 } 

可参考博客有更详细解释：https://blog.****.net/hushhw/article/details/78112719
（4）斐波那契数列

斐波纳契数列，又称黄金分割数列，指的是这样一个数列：1、1、2、3、5、8、13、21、……

这个数列从第三项开始，每一项都等于前两项之和。

有趣的兔子问题：

一般而言，兔子在出生两个月后，就有繁殖能力，一对兔子每个月能生出一对小兔子来。如果所有兔子都不死，那么一年以后可以繁殖多少对兔子？

分析如下：

第一个月小兔子没有繁殖能力，所以还是一对；

两个月后，生下一对小兔子，总数共有两对；

三个月以后，老兔子又生下一对，因为小兔子还没有繁殖能力，总数共是三对；

……

依次类推可以列出下表：

 //斐波那契
    long Fib(int n)
    {
     if (n == 0) 
      return 0;
     if (n == 1) 
      return 1;
     if (n > 1) 
      return Fib(n-1) + Fib(n-2);
    }

（4）判定一系列字符串中是否有相同的内容【JAVA代码】

public class T {
    public static void main(String[] args) {
        String[] a = {"a1","a2","a3","b3","c","b","33","33"};
        boolean b = new T().fun(0, a);
        System.out.println(b);
    }
    
    public boolean fun(int n,String[] a){
        boolean b = false;
        if(n == a.length){
            b = true;
        }else{
            for(int i = n; i < a.length-1; i++){
                System.out.println(n+"    "+(i+1));
                if(a[n].equals(a[i+1])){
                    return false;
                }
            }
            n++;
            fun(n,a);
        }
        return b;
    }
}