【蓝桥杯Java_C组·从零开始卷】第七节、递归
目录
递归概述
人理解迭代，神理解递归。毋庸置疑地，递归确实是一个奇妙的思维方式。对一些简单的递归问题，我们总是惊叹于递归描述问题的能力和编写代码的简洁，但要想真正领悟递归的精髓、灵活地运用递归思想来解决问题却并不是一件容易的事情。本文剖析了递归的思想内涵，分析了递归与循环的联系与区别，给出了递归的应用场景和一些典型应用，并利用递归和非递归的方式解决了包括阶乘、斐波那契数列、汉诺塔、杨辉三角的存取、字符串回文判断、字符串全排列、二分查找、树的深度求解在内的八个经典问题。
递归：
你打开面前这扇门，看到屋里面还有一扇门。你走过去，发现手中的钥匙还可以打开它，你推开门，发现里面还有一扇门，你继续打开它。若干次之后，你打开面前的门后，发现只有一间屋子，没有门了。然后，你开始原路返回，每走回一间屋子，你数一次，走到入口的时候，你可以回答出你到底用这你把钥匙打开了几扇门。
循环：
你打开面前这扇门，看到屋里面还有一扇门。你走过去，发现手中的钥匙还可以打开它，你推开门，发现里面还有一扇门（若前面两扇门都一样，那么这扇门和前两扇门也一样；如果第二扇门比第一扇门小，那么这扇门也比第二扇门小，你继续打开这扇门，一直这样继续下去直到打开所有的门。但是，入口处的人始终等不到你回去告诉他答案。
疑问：
什么是递归呢？
递归的精髓(思想)是什么？
递归和循环的区别是什么？
什么时候该用递归？
使用递归需要注意哪些问题？
递归思想解决了哪些经典的问题？
是什么递归？
定义
在数学与计算机科学中，递归(Recursion)是指在函数的定义中使用函数自身的方法。实际上，递归，顾名思义，其包含了两个意思：递 和 归，这正是递归思想的精华所在。
递归的精髓(思想)是什么?
正如上面所描述的场景，递归就是有去（递去）有回（归来），如下图所示。“有去”是指：递归问题必须可以分解为若干个规模较小，与原问题形式相同的子问题，这些子问题可以用相同的解题思路来解决，就像上面例子中的钥匙可以打开后面所有门上的锁一样；“有回”是指 : 这些问题的演化过程是一个从大到小，由近及远的过程，并且会有一个明确的终点(临界点)，一旦到达了这个临界点，就不用再往更小、更远的地方走下去。最后，从这个临界点开始，原路返回到原点，原问题解决。
更直接地说，递归的基本思想就是把规模大的问题转化为规模小的相似的子问题来解决。特别地，在函数实现时，因为解决大问题的方法和解决小问题的方法往往是同一个方法，所以就产生了函数调用它自身的情况，这也正是递归的定义所在。格外重要的是，这个解决问题的函数必须有明确的结束条件，否则就会导致无限递归的情况。
用归纳法来理解递归
数学都不差的我们，第一反应就是递归在数学上的模型是什么，毕竟我们对于问题进行数学建模比起代码建模拿手多了。观察递归，我们会发现，递归的数学模型其实就是 数学归纳法，这个在高中的数列里面是最常用的了，下面回忆一下数学归纳法。
数学归纳法适用于将解决的原问题转化为解决它的子问题，而它的子问题又变成子问题的子问题，而且我们发现这些问题其实都是一个模型，也就是说存在相同的逻辑归纳处理项。当然有一个是例外的，也就是归纳结束的那一个处理方法不适用于我们的归纳处理项，当然也不能适用，否则我们就无穷归纳了。总的来说，归纳法主要包含以下三个关键要素：
步进表达式：问题蜕变成子问题的表达式
结束条件：什么时候可以不再使用步进表达式
直接求解表达式：在结束条件下能够直接计算返回值的表达式
事实上，这也正是某些数学中的数列问题在利用编程的方式去解决时可以使用递归的原因，比如著名的斐波那契数列问题。
递归的三要素
在我们了解了递归的基本思想及其数学模型之后，我们如何才能写出一个漂亮的递归程序呢？笔者认为主要是把握好如下三个方面：
1、明确递归终止条件；
2、给出递归终止时的处理办法；
3、提取重复的逻辑，缩小问题规模。
1). 明确递归终止条件
我们知道，递归就是有去有回，既然这样，那么必然应该有一个明确的临界点，程序一旦到达了这个临界点，就不用继续往下递去而是开始实实在在的归来。换句话说，该临界点就是一种简单情境，可以防止无限递归。
2). 给出递归终止时的处理办法
我们刚刚说到，在递归的临界点存在一种简单情境，在这种简单情境下，我们应该直接给出问题的解决方案。一般地，在这种情境下，问题的解决方案是直观的、容易的。
3). 提取重复的逻辑，缩小问题规模*
我们在阐述递归思想内涵时谈到，递归问题必须可以分解为若干个规模较小、与原问题形式相同的子问题，这些子问题可以用相同的解题思路来解决。从程序实现的角度而言，我们需要抽象出一个干净利落的重复的逻辑，以便使用相同的方式解决子问题。
递归模型
在我们明确递归算法设计三要素后，接下来就需要着手开始编写具体的算法了。在编写算法时，不失一般性，我们给出两种典型的递归算法设计模型，如下所示。
递归基础案例
package Action;
public class demo {
public static void main(String[] args) {
f(10);
}
public static int f(int i){//参数
System.out.println(i);
if (i==0){ // 明确的递归终止条件
return 0; // 简单情景
} else { // 在将问题转换为子问题的每一步，解决该步中剩余部分的问题
i--; // 递去
return f(i);// 递到最深处后，不断地归来
}
}
}
递归的应用场景
在我们实际学习工作中，递归算法一般用于解决三类问题：
(1). 问题的定义是按递归定义的（Fibonacci函数，阶乘，…）；
(2). 问题的解法是递归的（有些问题只能使用递归方法来解决，例如，汉诺塔问题，…）；
(3). 数据结构是递归的（链表、树等的操作，包括树的遍历，树的深度，…）。
递归与循环
递归与循环是两种不同的解决问题的典型思路。递归通常很直白地描述了一个问题的求解过程，因此也是最容易被想到解决方式。循环其实和递归具有相同的特性，即做重复任务，但有时使用循环的算法并不会那么清晰地描述解决问题步骤。单从算法设计上看，递归和循环并无优劣之别。然而，在实际开发中，因为函数调用的开销，递归常常会带来性能问题，特别是在求解规模不确定的情况下；而循环因为没有函数调用开销，所以效率会比递归高。递归求解方式和循环求解方式往往可以互换，也就是说，如果用到递归的地方可以很方便使用循环替换，而不影响程序的阅读，那么替换成循环往往是好的。问题的递归实现转换成非递归实现一般需要两步工作：
(1). 自己建立“堆栈(一些局部变量)”来保存这些内容以便代替系统栈，比如树的三种非递归遍历方式；
(2). 把对递归的调用转变为对循环处理。
特别地，在下文中我们将给出递归算法的一些经典应用案例，对于这些案例的实现，我们一般会给出递归和非递归两种解决方案，以便读者体会。
经典递归问题实战
阶乘
package Action;
public class demo {
public static void main(String[] args) {
System.out.println(f(10));;
}
public static long f(int n) {
if (n == 1) { // 递归终止条件
return 1; // 简单情景
}
return n * f(n - 1); // 相同重复逻辑，缩小问题的规模
}
}
斐波纳契数列
/**
* Title: 斐波纳契数列
*
* Description: 斐波纳契数列，又称黄金分割数列，指的是这样一个数列：1、1、2、3、5、8、13、21、……
* 在数学上，斐波纳契数列以如下被以递归的方法定义：F0=0，F1=1，Fn=F(n-1)+F(n-2)（n>=2，n∈N*）。
*
* 两种递归解法：经典解法和优化解法
* 两种非递归解法：递推法和数组法
*
package Action;
public class demo {
public static void main(String[] args) {
System.out.println(f(10));
}
public static int f(int n) {
if (n == 1 || n == 2) { // 递归终止条件
return 1; // 简单情景
}
return f(n - 1) + f(n - 2); // 相同重复逻辑，缩小问题的规模
}
}
回文字符串的判断
回文字符串就是正读倒读都一样的字符串。如”98789”, “abccba”都是回文字符串
package Action;
public class demo {
public static void main(String[] args) {
System.out.println(f("952757259"));
}
public static boolean f(String s){
int start = 0;
int end = s.length()-1;
if(end > start){ // 递归终止条件:两个指针相向移动，当start超过end时，完成判断
if(s.charAt(start) != s.charAt(end)){
return false;
}else{
// 递归调用，缩小问题的规模
return f(s.substring(start+1).substring(0, end-1));
}
}
return true;
}
}
字符串全排列
从字符串数组中每次选取一个元素，作为结果中的第一个元素;然后，对剩余的元素全排列
package Action;
public class demo {
public static void main(String[] args) {
String s="abc";
f(s.toCharArray(),0,s.length()-1);
}
public static void f(char[] s, int from, int to) {
if (s != null && to >= from && to < s.length && from >= 0) { // 边界条件检查
if (from == to) { // 递归终止条件
System.out.println(s); // 打印结果
} else {
for (int i = from; i <= to; i++) {
swap(s, i, from); // 交换前缀,作为结果中的第一个元素，然后对剩余的元素全排列
f(s, from + 1, to); // 递归调用，缩小问题的规模
swap(s, from, i); // 换回前缀，复原字符数组
}
}
}
}
public static void swap(char[] s, int from, int to) {
char temp = s[from];
s[from] = s[to];
s[to] = temp;
}
}
二分查找
package Action;
public class demo {
/**
* @search 返回被查找的数的位置下标
* @param arr 查找的数组
* @param n 是要查找的数
* @param begin 低位
* @param end 高位
* @return
*/
public static int search(int []arr,int n,int begin ,int end){
int mid=(begin+end)/2;
if(n<arr[begin]||n>arr[end]||arr[begin]>arr[end]){
return -1;//结束
}
if(arr[mid]<n){
return search(arr, n, mid+1, end);
}
else if(arr[mid]>n){
return search(arr, n, begin, mid-1);
}else{
return mid;
}
}
public static void main(String[] args) {
int [] arr={1,2,3,4,5,6};
System.out.println(search(arr,2,0,arr.length-1));
System.out.println(search(arr,5,0,arr.length-1));
}
}
汉诺塔问题
/**
* Title: 汉诺塔问题
* Description:古代有一个梵塔，塔内有三个座A、B、C，A座上有64个盘子，盘子大小不等，大的在下，小的在上。
* 有一个和尚想把这64个盘子从A座移到C座，但每次只能允许移动一个盘子，并且在移动过程中，3个座上的盘子始终保持大盘在下，
* 小盘在上。在移动过程中可以利用B座。要求输入层数，运算后输出每步是如何移动的。
*/
package Action;
public class demo {
/**
* @description 在程序中，我们把最上面的盘子称为第一个盘子，把最下面的盘子称为第N个盘子
* @param level：盘子的个数
* @param from 盘子的初始地址
* @param inter 转移盘子时用于中转
* @param to 盘子的目的地址
*/
public static void moveDish(int level, char from, char inter, char to) {
if (level == 1) { // 递归终止条件
System.out.println("从" + from + " 移动盘子" + level + " 号到" + to);
return;
} else {
// 递归调用：将level-1个盘子从from移到inter(不是一次性移动，每次只能移动一个盘子,其中to用于周转)
moveDish(level - 1, from, to, inter); // 递归调用，缩小问题的规模
// 将第level个盘子从A座移到C座
System.out.println("从" + from + " 移动盘子" + level + " 号到" + to);
// 递归调用：将level-1个盘子从inter移到to,from 用于周转
moveDish(level - 1, inter, from, to); // 递归调用，缩小问题的规模
}
}
public static void main(String[] args) {
int nDisks = 10;
moveDish(nDisks, 'A', 'B', 'C');
}
}
从A 移动盘子1 号到C
从A 移动盘子2 号到B
从C 移动盘子1 号到B
从A 移动盘子3 号到C
从B 移动盘子1 号到A
从B 移动盘子2 号到C
从A 移动盘子1 号到C
这篇内容对初学者不是很友好，可以慢慢来。
- 点赞
- 收藏
- 关注作者
评论（0）