深入理解递归算法以及应用场景

超、凢脫俗 2023-02-09 05:26 53阅读 0赞

# 递归的思想 #

**以此类推是递归的基本思想。**

具体来讲就是把规模大的问题转化为规模小的相似的子问题来解决。在函数实现时，因为解决大问题的方法和解决小问题的方法往往是同一个方法，所以就产生了函数调用它自身的情况。另外这个解决问题的函数必须有明显的结束条件，这样就不会产生无限递归的情况了。

**递归的两个条件**：

**自身调用**：可以通过递归调用来缩小问题规模，且新问题与原问题有着相同的形式  
**递归出口**：存在一种简单情境，可以使递归在简单情境下退出。

# 怎么更好地理解递归算法 #

**递归**：你打开面前这扇门，看到屋里面还有一扇门（这门可能跟前面打开的门一样大小（静），也可能门小了些（动）），你走过去，发现手中的钥匙还可以打开它，你推开门，发现里面还有一扇门，你继续打开…… 若干次之后，你打开面前一扇门，发现只有一间屋子，没有门了。 你开始原路返回，每走回一间屋子，你数一次，走到入口的时候，你可以回答出你到底用这钥匙开了几扇门。递归就是有去（递去）有回（归来）。

**循环**：你打开面前这扇门，看到屋里面还有一扇门，（这门可能跟前面打开的门一样大小（静），也可能门小了些（动）），你走过去，发现手中的钥匙还可以打开它，你推开门，发现里面还有一扇门，（前面门如果一样，这门也是一样，第二扇门如果相比第一扇门变小了，这扇门也比第二扇门变小了（动静如一，要么没有变化，要么同样的变化）），你继续打开这扇门……一直这样走下去。 入口处的人始终等不到你回去告诉他答案。

# 应用场景 #

## 1.Fibonacci数列 ##

斐波那契数列就是如下的数列：  
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, …，  
总之，就是第N(N > 2)个数等于第(N - 1)个数和(N - 2)个数的和。用递归程序流程如下图：  
![程序流程][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1ZlZXJfYw_size_16_color_FFFFFF_t_70]

## 2. 阶乘 ##

例如在求解6的阶乘时，递归过程如下所示。  
![递归流程][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1ZlZXJfYw_size_16_color_FFFFFF_t_70 1]  
这个过程和栈的工作原理一致对，递归调用就是通过栈这种数据结构完成的。整个过程实际上就是一个栈的入栈和出栈问题。然而我们并不需要关心这个栈的实现，这个过程是由系统来完成的。  
那么递归中的“递”就是入栈，递进；“归”就是出栈，回归。

## 3 .汉诺塔问题 ##

汉诺塔问题是源于印度一个古老传说的益智玩具。大梵天创造世界的时候做了三根金刚石柱子，在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘。大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定，在小圆盘上不能放大圆盘，在三根柱子之间一次只能移动一个圆盘。

import java.util.*;
    public class HanoiTower { 
        public static int yidongcishu=0;
        public static void main(String[] args) { 
        while(true){ 
        Scanner read=new Scanner(System.in);
        int cishu=read.nextInt();
            hanoiTower(cishu, 'A', 'B', 'C');
            System.out.println("移动的总次数为："+yidongcishu+"次。");
            yidongcishu=0;
        }}
        private static void hanoiTower(int num, char a, char b, char c) { 
            if (num == 1) {  // 只有一个盘，直接解出
                System.out.println("第1个盘从" + a + "->" + c);
                yidongcishu++;
            } else { 
                // 如果n>=2的情况
                // 1.先把最上面的所有盘A->B，移动过程会使用C
                hanoiTower(num - 1, a, c, b);
                // 2.把最下边的盘A->C
                System.out.println("第" + num + "个盘从" + a + "->" + c);
                            yidongcishu++;
                // 3.把B塔所有盘从B->C，移动过程使用到A
                hanoiTower(num - 1, b, a, c);
            }
        }
    }

程序运行结果如下图所示：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1ZlZXJfYw_size_16_color_FFFFFF_t_70 2]

## 4. 排列组合 ##

对于一个长度为n的串或者n个字符(数字、节点)组成的字符串数组，它的全排列共有A(n, n)=n!种。这个问题也是一个递归的问题。如1,2,3，全排列可得到：\{123,132,213,231,312,321\}，输出任意个数字母、数字的全排列 。

## 5.归并排序 ##

归并排序也是递归的典型应用，其思想：将序列分为若干有序序列（开始为单个记录），两个相邻有序的序列合并成一个有序的序列，以此类推，直到整个序列有序。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1ZlZXJfYw_size_16_color_FFFFFF_t_70 3]  
归并排序（Merge）是将两个（或两个以上）有序表合并成一个新的有序表，即把待排序序列分为若干个子序列，每个子序列是有序的。然后再把有序子序列合并为整体有序序列。

归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。 将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为2-路归并。

归并排序算法稳定，数组需要O(n)的额外空间，链表需要O(log(n))的额外空间，时间复杂度为O(nlog(n))，算法不是自适应的，不需要对数据的随机读取。

**工作原理：**

1.申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列；  
2.设定两个指针，最初位置分别为两个已经排序序列的起始位置；  
3.比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置；  
4.重复步骤3直到某一指针达到序列尾；  
5.将另一序列剩下的所有元素直接复制到合并序列尾。

## 6 .趣味问题——年龄。 ##

有5个人坐在一起，问第五个人多少岁？他说比第4个人大2岁。问第4个人岁数，他说比第3个人大2岁。问第三个人，又说比第2人大两岁。问第2个人，说比第一个人大两岁。最后问第一个人，他说是10岁。请问第五个人多大？

## 7.和数分解 ##

把一个数分解成任意几个数的和，把所有的可能性列出来。

import java.util.*;
    public class HeShiFenJie { 
    	/* *@author Chao */
    	static int sum = 0;//和
    	static int pos = -1;//指针
    	static int number = 0;//输入的数
    	static int[] reslut;
        static int count = 0;//解的次数
    	public static void main(String[] args) { 
    		Scanner read = new Scanner(System.in);
    		while(read.hasNext()){ 
            number = read.nextInt();
    		reslut = new int[number];
    		DFS(1);
            System.out.println("您好：根据要求，共有"+count+"数据和为"+"number");
            count = 0;
            }
    	}
    	private static void DFS(int x) { 
    		if (sum == number) { // 得到一组解
    			count++;
    			System.out.print(number + "=");
    			for (int i = 0; i < pos; i++) { // 输出前pos-1个元素
    				System.out.print(reslut[i] + "+");
    			}
    				System.out.println(reslut[pos]+";");//输出第pos个元素，换行
    			return;// 返回上一层
    		}
    		if (sum > number) { //未满足要求
    			return;
    		}
    		for (int i = x; i < number + 1; i++) { //把i的初值赋为x，目的就是保持序列自增
    			reslut[++pos] = i;// 要先自增再赋值，也会减少中间变量，节省空间
    			sum += i;
    			DFS(i);// 递归
    			pos--;// 指针回到前一位置
    			sum -= i;//相当于抵消上一次求和
    		}
    	}
    }

程序运行结果如下图所示：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1ZlZXJfYw_size_16_color_FFFFFF_t_70 4]

### 路阻且长之Java学习： ###

**[API中的重要类（一）：][API]  
https://blog.csdn.net/Veer\_c/article/details/103803248  
[API中的重要类（二）：][API 1]  
https://blog.csdn.net/Veer\_c/article/details/103807515  
[API中的重要类（三）：][API 2]  
https://blog.csdn.net/Veer\_c/article/details/103808054**

**[Java中的IO流（一）：][Java_IO]  
https://blog.csdn.net/Veer\_c/article/details/103833045  
[Java中的IO流（二）：][Java_IO 1]  
https://blog.csdn.net/Veer\_c/article/details/103833423  
[Java中的IO流（三）：][Java_IO 2]  
https://blog.csdn.net/Veer\_c/article/details/103833811**

**[Java多线程（一）：][Java]  
https://blog.csdn.net/Veer\_c/article/details/103842078  
[Java多线程（二）：][Java 1]  
https://blog.csdn.net/Veer\_c/article/details/103842263  
[Java多线程（三）：][Java 2]  
https://blog.csdn.net/Veer\_c/article/details/103842317  
[Java多线程（四）：][Java 3]  
https://blog.csdn.net/Veer\_c/article/details/103842602**

**[网络编程上（UDP）：][UDP]  
https://blog.csdn.net/Veer\_c/article/details/103843591  
[网络编程下（TCP）：][TCP]  
https://blog.csdn.net/Veer\_c/article/details/103843825**

**[MySQL数据库（一）：][MySQL]  
https://blog.csdn.net/Veer\_c/article/details/103844059  
[MySQL数据库（二）：][MySQL 1]  
https://blog.csdn.net/Veer\_c/article/details/103844537  
[MySQL数据库（三）：][MySQL 2]  
https://blog.csdn.net/Veer\_c/article/details/103844739**

**[JDBC技术（一）：][JDBC]  
https://blog.csdn.net/Veer\_c/article/details/103845176  
[JDBC技术（二）：][JDBC 1]  
https://blog.csdn.net/Veer\_c/article/details/103879890  
[JDBC技术（三）：][JDBC 2]  
https://blog.csdn.net/Veer\_c/article/details/103880021  
[JDBC技术（四）：][JDBC 3]  
https://blog.csdn.net/Veer\_c/article/details/103882264**

**[HTML的基础框架（一）：][HTML]  
https://blog.csdn.net/Veer\_c/article/details/103882385  
[HTML的基础框架（二）：][HTML 1]  
https://blog.csdn.net/Veer\_c/article/details/103882684**

**[CSS入门（一）][CSS]  
https://blog.csdn.net/Veer\_c/article/details/103882856**  
**[CSS入门（二）：][CSS 1]  
https://blog.csdn.net/Veer\_c/article/details/103883102**

**[JavaScript实用案例与常见问题（一）：][JavaScript]  
https://blog.csdn.net/Veer\_c/article/details/103894959  
[JavaScript实用案例及常见问题（二）：][JavaScript 1]  
https://blog.csdn.net/Veer\_c/article/details/103895166**

**[BOM编程详解：][BOM]  
https://blog.csdn.net/Veer\_c/article/details/103895433**

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1ZlZXJfYw_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200518140509910.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1ZlZXJfYw==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1ZlZXJfYw_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200518140753577.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1ZlZXJfYw==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1ZlZXJfYw_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20200518144656709.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1ZlZXJfYw==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1ZlZXJfYw_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/20200518143715673.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1ZlZXJfYw==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1ZlZXJfYw_size_16_color_FFFFFF_t_70 4]: https://img-blog.csdnimg.cn/20200518144348960.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1ZlZXJfYw==,size_16,color_FFFFFF,t_70
[API]: https://blog.csdn.net/Veer_c/article/details/103803248
[API 1]: https://blog.csdn.net/Veer_c/article/details/103807515
[API 2]: https://blog.csdn.net/Veer_c/article/details/103808054
[Java_IO]: https://blog.csdn.net/Veer_c/article/details/103833045
[Java_IO 1]: https://blog.csdn.net/Veer_c/article/details/103833423
[Java_IO 2]: https://blog.csdn.net/Veer_c/article/details/103833811
[Java]: https://blog.csdn.net/Veer_c/article/details/103842078
[Java 1]: https://blog.csdn.net/Veer_c/article/details/103842263
[Java 2]: https://blog.csdn.net/Veer_c/article/details/103842317
[Java 3]: https://blog.csdn.net/Veer_c/article/details/103842602
[UDP]: https://blog.csdn.net/Veer_c/article/details/103843591
[TCP]: https://blog.csdn.net/Veer_c/article/details/103843825
[MySQL]: https://blog.csdn.net/Veer_c/article/details/103844059
[MySQL 1]: https://blog.csdn.net/Veer_c/article/details/103844537
[MySQL 2]: https://blog.csdn.net/Veer_c/article/details/103844739
[JDBC]: https://blog.csdn.net/Veer_c/article/details/103845176
[JDBC 1]: https://blog.csdn.net/Veer_c/article/details/103879890
[JDBC 2]: https://blog.csdn.net/Veer_c/article/details/103880021
[JDBC 3]: https://blog.csdn.net/Veer_c/article/details/103882264
[HTML]: https://blog.csdn.net/Veer_c/article/details/103882385
[HTML 1]: https://blog.csdn.net/Veer_c/article/details/103882684
[CSS]: https://blog.csdn.net/Veer_c/article/details/103882856
[CSS 1]: https://blog.csdn.net/Veer_c/article/details/103883102
[JavaScript]: https://blog.csdn.net/Veer_c/article/details/103894959
[JavaScript 1]: https://blog.csdn.net/Veer_c/article/details/103895166
[BOM]: https://blog.csdn.net/Veer_c/article/details/103895433