递归问题剖析

左手的ㄟ右手 2022-07-16 08:39 154阅读 0赞

**原来大一时只是简单接触了递归，但是并没有做深入的思考和理解。如今决定在算法上下一番功夫，所以翻出来再次学习，并做此总结。**

**递归最深层次的精髓我感觉我还不能真正掌握，个人认为这需要大脑具备强大的逻辑推理能力，能够实现凭空的推演。这里总结的只是递归的运用。**

**满足使用递归的条件为1.有反复执行的过程2.有跳出反复执行的条件。因此在如何编写递归代码也之需两步：1.写出结束循环的条件（一般为正向循环的起始步骤）2.调用自身的语句（一般可以正向思考，简化问题，第一次循环过程的步骤）**

**下面是一些经典实战例题：**

**（1）阶乘  
  
n! = n \* (n-1) \* (n-2) \* ...\* 1(n>0)**

int jiecheng(int n)
    {
    	
    	if(n==1) return 1;
    	else
    	return n*jiecheng(n-1);
    
    }

**（2）斐波那契数列  
  
斐波纳契数列，又称黄金分割数列，指的是这样一个数列：1、1、2、3、5、8、13、21、……  
  
这个数列从第三项开始，每一项都等于前两项之和。**

int fun(int n)
    {
    	if(n==1) return 1;
    	if(n==2) return 1;
    	return fun(n-1)+fun(n-2);
    
    }

（3）汉诺塔问题

**每次只能移动一个盘，大盘不能放到小盘上面。**

**（分析：正向思考，结束条件为只有一个盘的情况，即把盘从一放到三；调用自身语句为两个盘的情况，即把小盘从一放到二，把大盘从一放到三，把小盘从二放到三。即使盘数增加，循环不变。注意循环中改变了参数p1,p2,p3的顺序****）**

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);
    	}
    }

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

#include <iostream>
    using namespace std;
    int len;
    int *p=new int[len];
    
    void swap(int a,int b)
    {int temp;
    temp=p[a];
    p[a]=p[b];
    p[b]=temp;}
    void perm(int *arr,int begin,int end)
    {
    	if(begin==end) 
    	{
    		for(int i=0;i<len;i++)
    			cout<<arr[i];
    		cout<<endl;
    	}
    	else
    	{
    		for(int j=begin;j<=end;j++)
    		{
    			swap(j,begin);
    			perm(arr,begin+1,end);
    			swap(j,begin);
    		}
    	}
    }
    int main()
    {
    	cin>>len;
    	for(int i=0;i<len;i++)
    		cin>>p[i];
    	perm(p,0,len-1);
    	return 0;
    }