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