经典算法之——递归

拼搏现实的明天。 2023-10-10 19:38 2阅读 0赞

> 说明

**在编程中，递归是一种在计算机科学通过某个重复将问题分解为同类的子问题并不断的解决子问题的一种方式。通过在编程语言中的函数里可以通过调用自身来进行递归。而在计算理论中，可以证明递归的作用可以完全取代循环，因此在很多函数编程语言中习惯用递归来实现循环。**

而单单的说递归话，就是函数调用自身那么简单，但是在真正的实现过程或者解决实际问题中，并没有那么简单，所设计的范围与应用的场景还是比较广的。

> 介绍

`就拿5的阶乘来举例：像下面这种方式就是属于 向下 ‘递’`

5!=5*4!
    4!=4*3!
    3!=3*2!
    2!=2*1!

`当我们需要回 '归'时，就好像这样的形式,利用函数的特性不断return，最后求出5!`

f(5)=5*f(4)
    f(4)=4*f(3)
    f(3)=3*f(2)
    f(2)=2*f(1)
    f(1)=1

其实斐波那契数列算法也可以更好的说明简单的递归形式。

这里介绍几个属于递归的几种形式算法

## 深度优先算法(DFS) ##

> 介绍

深度优先搜索属于图算法的一种。其过程简要来说是对每一个可能的分支路径深入到不能再深入为止，而且每个节点只能访问一次。

> 思想

a.访问顶点A；  
b.依次从顶点r的未被访问的邻接点出发，对图进行深度优先遍历；直至图中和顶点A有路径相通的顶点都被访问；  
c.若此时图中尚有顶点未被访问，则从一个未被访问的顶点出发，重新进行深度优先遍历，直到图中所有顶点均被访问过为止。  
![在这里插入图片描述][383c61f2b92e48079eac9e99aad55ca8.jpeg_pic_center]  
不难看出其实这种也是从上面进行向下‘`递`’，完成任务之后又会回 ‘`归`’,这里就引一道算法来说明

> 题目：1—n所有可能会取的值,求方案数

--------------------

![在这里插入图片描述][5758335dcfbe47999fc0ba4d0d45ca6e.png]

#include<iostream>
    using namespace std;
    const int N=16;
    int st[N];//st数组有三种值，1表示选，2表示不选，0表示初始状态
    int n;
    void dfs(int u){
        //  u代表我们枚举到第u个数
        if(u>n){
        //当刚刚等于n时还没有完成n这个数，大于n时才枚举完了就开始打印
            for(int i=1;i<=n;i++){
        
                if(st[i]==1) cout<<i<<" ";
            }
            cout<<endl;
            return; //完成一次任务之后，开始回 ‘归’
        }
        /**
        递归下一个口，为左叶子和右叶子，即有选和不选两种可能
        */
        st[u]=2;//   不选
        dfs(u+1);//枚举下一个数
        st[u]=0;//恢复现场
        
        st[u]=1;//    选
        dfs(u+1);//枚举下一个数
        st[u]=0;//恢复现场
    }
    int main()
    {
        
        cin>>n;
        dfs(0);// 开始向下‘递’
        return 0;
    }

可以看到深度优先可以就是递归的一种形式

## 广度优先算法（BFS） ##

广度优先算法又称广度优先搜索，是一种图形搜索演算法。BFS是从根节点开始，沿着树的宽度遍历树的节点，如果发现目标，则演算终止。广度优先搜索的实现一般采用open-closed表。  
`同样为一颗二叉树为例子`  
![在这里插入图片描述][e63fd9ba26964c9d835488a99e03fdf1.png]  
`步骤:`  
1=>2,返回到结点1，然后1=>3,返回到1；然后从2判断相邻的结点4,5结点，然后2=>4,返回到2，2=>5,这时左子树已经完成了没有结点可以遍历了；接下来到右子树, 3=>6,然后返回到3，再3=>7，右子树遍历完成，结束。

--------------------

> 例题:  
> 一矩形阵列由数字0到9组成,数字1到9代表细胞,细胞的定义为沿细胞数字上下左右还是细胞数字则为同一细胞,求给定矩形阵列的细胞个数。

4 10
    [n]x[m]矩阵
    0234500067
    1034560500
    2045600671
    0000000089
    【输出样例】
    4

/**
        *   (bfs)细胞分裂----一矩形阵列由数字 0 到 9 组成，数字 1 到 9 代表细胞，
        *    细胞的定义为沿细胞数字上下左右若还是细胞数字则为同一细胞，求给定矩形阵列的细胞个数。
        * 
        */
    	static int ant=0;
    	public static void main(String[] args) {
        
          Scanner scanner=new Scanner(System.in);
          int n=scanner.nextInt();
          int m=scanner.nextInt();
          int[][] array=new int[n][m];
          for (int i = 0; i < n; i++) {
        
    		for (int j = 0; j <m; j++) {
        
    			array[n][m]=scanner.nextInt();
    		}
    	}
     	 
      	for (int i = 0; i < array.length; i++) {
        
      		for (int j = 0; j < array[0].length; j++) {
        
      			  ++ant;
      			  bfs(array,i,j); //从第ant个入口递归
      		 }
        	}
      	System.out.println(ant);
    	}
    /**
       实现广度优先的部分
    */
    private static void bfs(int[][] array,int y,int x) {
        
    	// TODO Auto-generated method stub
    	if (x>=array[0].length||x<0||y<0||y>=array.length||array[y][x]==0) {
         //递归出口
    		return;
    	}
    	array[y][x]=0;  //重点：将走过的路变为0，
    	bfs(array, y-1, x);
    	bfs(array, y+1, x);
    	bfs(array, y, x-1);
    	bfs(array, y, x+1);
     }

`这里就是利用了从某个结点开始，然后上下左右开始探索路，并将走过的路标记好，当发现这条路走不通了，就原路返回到原来结点，开始走新的一条路。`

## 动态规划 ##

这是一种强大的算法设计技术——可以将问题分解成多个子问题，并在过程中存储它们的结果，为了避免子问题的重复计算，保证每个子问题只求解一次，会将解保存在数组中，并在最后中可以很好的拿到原始想要的数据，又可以展示整个解决过程,通常在解题的过程中，起名为dp。

在这一类的算法中，难度还是比较中上的，比较适合有一定算法能力和思维的上手,我这里就是简单提一下，就是做一个递归的了解

> 展示图

`为一个二维数组的形式实现的普通DP`

![在这里插入图片描述][5b1d26f9957942c5b0b520b5e8d2ef77.png_pic_center]

> 题目：  
> 有一个背包，容量是C，有若干个物品，价值各不相同，  
> 重量也各不相同。接下来请你选择一部分物品装入背包，  
> 要保证不超过背包的容量的前提下，使背包中物体的总价值最大。

![在这里插入图片描述][be2c89aee31542178c526f19e59c04f1.png]

public static void main(String[] args) {
        
        int[] weight={
        1,4,3};
        int[] value={
        1500,3000,2000};
        int m=4;//背包的容量
        int n=value.length;// 物品的个数
    
        // 记录商品的情况
       int[][] path=new int[n+1][n+1];
    
        //创建二维数组
        int[][] v=new int[n+1][n+1];
    
        // 初始化第一列和第一行
        for(int i=0;i<v.length;i++){
        
           v[i][0]=0;
        }
        for(int i=0;i<v[0].length;i++){
        
          v[0][i]=0;
        }
    
        //开始处理公式得到的动态规划
        for(int i=1;i< v.length;i++){
        
          for(int j=1;j<v[0].length;j++){
        
            if(weight[i-1]>j){
        //新加入的商品容量大于了背包的容量，我们则加入的是是一个的物品（可以为空）
              v[i][j]=v[i-1][j];
            }
            else {
         // 加入新商品之后还有剩余空间时，我们则加入能满足这个空间大小的最大价值物品
    //           v[i][j]=Math.max(v[i-1][j],value[i-1]+v[i-1][j-weight[i-1]]);//从物品的第一个开始
              /**
               * 为了记录商品的存放到背包的情况
               */
                  if(v[i-1][j]<value[i-1]+v[i-1][j-weight[i-1]]){
        
                    v[i][j]=(value[i-1]+v[i-1][j-weight[i-1]]);
                    path[i][j]=1;
                  }else {
        
                    v[i][j]=v[i-1][j];
                  }
            }
          }
        }
        for(int index=0;index< v.length;index++){
        
          for(int index1=0;index1<v[index].length;index1++){
        
            System.out.print(v[index][index1]+" ");
          }
          System.out.println();
        }
         int i=path.length-1;// 行
        int j=path[0].length-1;// 列
        while (i>0&&j>0){
        
            if(path[i][j]==1){
        
                System.out.println("第"+i+"个商品放入背包/n");
                j=j-weight[i-1];
            }
            i--;
        }
      }

`这部分有兴趣的朋友可以找其他资料进行一个深度学习`

> 总结

总之，递归这部分还是非常的重要的，无论是在算法能力和思维培养，还是在程序设计中，都有很大的帮助。  
![在这里插入图片描述][3ff169d510c54ab4a246c4a7e4ec6e78.png]  
这里可以看到递归以及递归的其他应用是年年都在考，可见它在算法中的一个地位如何了。

[383c61f2b92e48079eac9e99aad55ca8.jpeg_pic_center]: https://img-blog.csdnimg.cn/383c61f2b92e48079eac9e99aad55ca8.jpeg#pic_center
[5758335dcfbe47999fc0ba4d0d45ca6e.png]: https://img-blog.csdnimg.cn/5758335dcfbe47999fc0ba4d0d45ca6e.png
[e63fd9ba26964c9d835488a99e03fdf1.png]: https://img-blog.csdnimg.cn/e63fd9ba26964c9d835488a99e03fdf1.png
[5b1d26f9957942c5b0b520b5e8d2ef77.png_pic_center]: https://img-blog.csdnimg.cn/5b1d26f9957942c5b0b520b5e8d2ef77.png#pic_center
[be2c89aee31542178c526f19e59c04f1.png]: https://img-blog.csdnimg.cn/be2c89aee31542178c526f19e59c04f1.png
[3ff169d510c54ab4a246c4a7e4ec6e78.png]: https://img-blog.csdnimg.cn/3ff169d510c54ab4a246c4a7e4ec6e78.png