【Java】经典递归专项题图文讲解(详解经典汉诺塔问题)

简介: 【Java】经典递归专项题图文讲解(详解经典汉诺塔问题)

image.png

【☕Java】经典递归专项题图文讲解(详解经典汉诺塔问题)

⭐递归求N的阶乘

⭐递归求1加到10

⭐递归返回一个非负整数组成它数字之和

⭐按顺序打印一个数字的每一位

⭐递归求斐波那契数列第N项 【时间复杂度O(2^N),空间复杂度O(n)】

⭐高效递归求斐波那契数列 【时间复杂度O(n),空间复杂度O(1)】

🌟🌟🌟求解汉诺塔问题

⭐递归求N的阶乘

思路:

这题主要就是要找到递归公式,阶乘的递归公式还是很好找的,较为明显

递归公式为 n ×(n-1)!

终止条件为 n==1


image.png

image.png

image.png

⭐递归求1加到10

思路:

从10开始,10+9+8+7……+2+1,这里依旧和上题一样,找到递归公式套娃就完了,相当于1~10的和等于 10 +(1~9的和 ),1~9的和又等于 9 +(1~8的和)一直到1,返回1
递归公式:n + Add(n-1)
终止条件: n == 1

image.png

image.png

image.png

⭐递归返回一个非负整数组成它数字之和

思路:

依旧是套娃,利用【%10】来求每位上的数,用【/10】来进入下一次调用,重复【%10】求下一位上的数,然后相加,触底后依次返回和
递归公式:n + AddSum(n/10)
终止条件: n < 10

image.png

image.png

image.png

⭐按顺序打印一个数字的每一位

思路:

这个题难想就在于它要按顺序打印每一位,你得先【/10】递归到它的最高位那一层,然后【%10】打印这一位上的数,再返回到上一层,打印倒数第二位上的数,依次返回到第一层,也就是打印个位上的数那一层
递归公式:n/10
终止条件:n<9

image.png

image.png

image.png

⭐递归求斐波那契数列第N项 【时间复杂度O(2^N),空间复杂度O(n)】

思路:

斐波那契数列是很经典的递归题,有多种方法,这里主要讲讲递归,普通的递归很容易想,前两项相加得到第三项,就这么简单,只不过这种递归时间复杂太高,不建议使用这种方法,但是可以帮助学习理解递归的意义

递归公式:Fib (n) = Fib(n-1) + Fib(n-2)

终止条件: n == 1 || n == 2 || n == 3

image.png

image.png

image.png

⭐高效递归求斐波那契数列 【时间复杂度O(n),空间复杂度O(1)】

思路:

如果说前一种递归解法是由后向前计算,那么这种解法就是由前向后计算了,这种递归方式属于尾递归,因此在进行递归时函数只会使用第一次压栈所开辟的栈空间,在一个栈空间内循环,而不会开辟别的栈空间,所以这种方式时间复杂度为O(N),空间复杂度为O(1),是一种非常高效的递归方式。

递归公式:Fib(sec , first+sec , n-1);

终止条件: n == 1


image.png

🌟🌟🌟求解汉诺塔问题

image.png

思路:

对于这样一个问题,任何人都不可能直接写出移动盘子的每一步,但我们可以利用下面的方法来解决。

设移动盘子数为n,为了将这n个盘子从A杆移动到C杆,可以做以下三步:

(1)以C盘为中介,从A杆将1至n-1号盘移至B杆;

(2)将A杆中剩下的第n号盘移至C杆;

(3)以A杆为中介;从B杆将1至n-1号盘移至C杆。

实际操作中,只有第二步可直接完成,而第一、三步又成为移动的新问题。以上操作的实质是把移动n个盘子的问题转化为移动n-1个盘,事实上,上述方法设盘子数为n, n可为任意数,该法同样适用于移动n-1个盘。因此,依据上述方法,可解决n -1个盘子,从A杆移到B杆(第一步)或从B杆移到C杆(第三步)问题。现在,问题由移动n个盘子

的操作转化为移动n-2个盘子的操作。依据该原理,层层递推,即可将原问题转化为解决移动n -2、n -3… … 3、2,直到移动1个盘的操作,而移动一个盘的操作是可以直接完成的。

递归公式:

hanoi(n - 1, start, end, tmp);

求解汉诺塔问题.move(n, start, end);

hanoi(n - 1, tmp,start , end);

终止条件:

盘子只剩一个,也就是n==1

image.png

   import java.util.Scanner;
   public class 求解汉诺塔问题 {
       static int count = 0;// 标记移动次数
       // 实现移动的函数
      public static void move(int disks, char start, char end) {
           //将盘子从小到大编号,每次将编号为disks的盘子,从start柱子移动到end柱子
           System.out.println("第" + (++count) + " 次移动 : " + " 把 " + disks + " 号圆盘从 " + start + " ->移到->  " + end );
       }
       // 递归实现汉诺塔的函数
                     //传入数据     n         A            B         C
       public static void hanoi(int n, char start , char tmp, char end) { //start是起点塔,tmp是过渡塔,end是终点塔
          if (n == 1)// 圆盘只有一个时,只需将其从A塔移到C塔
               求解汉诺塔问题.move(1, start, end);// 将编号为1的圆盘从A塔移到C塔
           else
           {
               // 否则
               hanoi(n - 1, start, end, tmp);// 递归,把A塔上编号1~n-1的圆盘移到B上,以C为过渡塔
               求解汉诺塔问题.move(n, start, end);// 把A塔上编号为n的圆盘移到C上
               hanoi(n - 1, tmp,start , end);// 递归,把B塔上编号1~n-1的圆盘移到C上,以A为过渡塔
           }
       }
       public static void main(String[] args) {
           Scanner in = new Scanner(System.in);
           char A = 'A';
           char B = 'B';
           char C = 'C';
           System.out.print("请输入圆盘的个数:");
          int n = in.nextInt();
          求解汉诺塔问题.hanoi(n, A, B, C);
          System.out.println(">>移动了" + count + "次,把A上的圆盘都移动到了C上");
         in.close();
     }
   }


image.png




相关文章
|
2月前
|
Java
java基础(11)函数重载以及函数递归求和
Java支持函数重载,即在同一个类中可以声明多个同名方法,只要它们的参数类型和个数不同。函数重载与修饰符、返回值无关,但与参数的类型、个数、顺序有关。此外,文中还展示了如何使用递归方法`sum`来计算两个数之间的和,递归的终止条件是当第一个参数大于第二个参数时。
30 1
java基础(11)函数重载以及函数递归求和
|
6月前
|
Java
java中递归实例
java中递归实例
44 0
|
4月前
|
算法 Java
java使用递归及迭代方式实现前序遍历 中序遍历 后序遍历 以及实现层序遍历
java使用递归及迭代方式实现前序遍历 中序遍历 后序遍历 以及实现层序遍历
81 7
|
5月前
|
Java
蓝桥杯Java组暴力递归搜图
蓝桥杯Java组暴力递归搜图
32 4
|
5月前
|
Java
java实现斐波那契数列(递归、迭代、流)
java实现斐波那契数列(递归、迭代、流)
|
5月前
|
算法 前端开发 Java
探讨Java中递归构建树形结构的算法
探讨Java中递归构建树形结构的算法
59 1
|
5月前
|
Java
Java递归:深入理解与应用
Java递归:深入理解与应用
67 1
|
5月前
|
存储 Java
Java基础手册(标识符 关键字 字面值 变量 数据类型 字符编码 运算符 控制语句 方法及方法重载和递归 面向对象与面向过程)
Java基础手册(标识符 关键字 字面值 变量 数据类型 字符编码 运算符 控制语句 方法及方法重载和递归 面向对象与面向过程)
37 0
|
5月前
|
Java 大数据 程序员
老程序员分享:java递归
老程序员分享:java递归
26 0
|
6月前
|
Java
<Java SE> 5道递归计算,创建数组,数组遍历,JVM内存分配...
<Java SE> 5道递归计算,创建数组,数组遍历,JVM内存分配
59 2