⭐按顺序打印一个数字的每一位
思路：
这个题难想就在于它要按顺序打印每一位，你得先【/10】递归到它的最高位那一层，然后【%10】打印这一位上的数，再返回到上一层，打印倒数第二位上的数，依次返回到第一层，也就是打印个位上的数那一层
递归公式：n/10
终止条件：n<9
图解
代码实现：
public class 按顺序打印一个数字的每一位 { public static void printNum (int n) { if(n > 9){ printNum(n / 10); } System.out.println(n % 10); //先递归，到底之后从后往前再打印 } public static void main(String[] args) { int n = 12345; printNum(n); } }
运行结果：
⭐递归求斐波那契数列第N项 【时间复杂度O(2^N),空间复杂度O(n)】
思路：
斐波那契数列是很经典的递归题，有多种方法，这里主要讲讲递归，普通的递归很容易想，前两项相加得到第三项，就这么简单，只不过这种递归时间复杂太高，不建议使用这种方法，但是可以帮助学习理解递归的意义
递归公式：Fib (n) = Fib(n-1) + Fib(n-2)
终止条件： n == 1 || n == 2 || n == 3
图解：
代码实现：
import java.util.Scanner; public class 递归求斐波那契数列第N项 {//时间复杂度O(2^N),空间复杂度O(n) public static int Fib(int n) { if (n==1) return 0; else if (n==2||n==3) return 1; return Fib(n-1) + Fib(n-2); } public static void main(String[] args) { Scanner scn = new Scanner(System.in); int n = scn.nextInt(); System.out.println ("第"+n+"个斐波那契数是"+Fib(n)); } }
运行结果：
⭐高效递归求斐波那契数列 【时间复杂度O(n)，空间复杂度O(1)】
思路：
如果说前一种递归解法是由后向前计算，那么这种解法就是由前向后计算了，这种递归方式属于尾递归，因此在进行递归时函数只会使用第一次压栈所开辟的栈空间，在一个栈空间内循环，而不会开辟别的栈空间，所以这种方式时间复杂度为O(N)，空间复杂度为O(1)，是一种非常高效的递归方式。
递归公式：Fib(sec , first+sec , n-1);
终止条件： n == 1
代码实现：
import java.util.Scanner; public class 高效递归求斐波那契数列 { //时间复杂度O(n)，空间复杂度O(1) public static int Fib(int first,int sec,int n) { if (n==1) return first; else return Fib(sec,first+sec,n-1); } public static void main(String[] args) { Scanner scn = new Scanner(System.in); int n = scn.nextInt(); System.out.println("第"+n+"个斐波那契数是"+Fib(0,1,n)); } }
🌟🌟🌟求解汉诺塔问题
问题介绍：
相传在古印度圣庙中，有一种被称为汉诺塔(Hanoi)的游戏。该游戏是在一块铜板装置上，有三根杆(编号A、B、C)，在A杆自下而上、由大到小按顺序放置64个金盘(如下图)。游戏的目标：把A杆上的金盘全部移到C杆上，并仍保持原有顺序叠好。操作规则：每次只能移动一个盘子，并且在移动过程中三根杆上都始终保持大盘在下，小盘在上，操作过程中盘子可以置于A、B、C任一杆上。
思路：
对于这样一个问题，任何人都不可能直接写出移动盘子的每一步，但我们可以利用下面的方法来解决。
设移动盘子数为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(); } }
运行结果：
