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

⭐递归求N的阶乘

⭐递归求1加到10

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

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

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

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

????????????求解汉诺塔问题

⭐递归求N的阶乘

思路：

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

递归公式为 n ×（n-1）！

终止条件为 n==1

⭐递归求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

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

思路：

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

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

思路：

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

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

思路：

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

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

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

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

思路：

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

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

终止条件： n == 1

????????????求解汉诺塔问题

思路：

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

设移动盘子数为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

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

   }