• 递归详解~


    目录

    一、什么是递归?

    二、递归练习 

    1、按位输出一个整数

    2、递归求 N 的阶乘 

    3、返回的数字之和 

    三、汉诺塔问题 

    一、什么是递归?

    递归:一个方法中又包含了本身。 

    通俗来说,递归就是自身中又包含了自己,是将一个原问题题分成若干子小问题,子问题与原问题的解法是一致的。

    构成递归的两个必要条件 :

    1. 要有递归出口,否则就会进入死循环。
    2. 将原问题划分为若干子问题,原问题要与子问题的解法一致。

    解决递归问题的关键是要求出递推公式。 

    二、递归练习 

    1、按位输出一个整数

    问题描述:将一个整数按位输出,例如:123 输出结果为:1 2 3 

    思路分析: 对于按位输出,首先要输出的是最高位,就是对该整数不断整除10,直到小于10,这就是递归出口,对于其他位我们可以输出对10取模,那么我们就可以使用递归来解决。

    代码实现 :

    1. public static void printNum(int n){
    2. if(n<10){
    3. System.out.print(n+" ");
    4. return;
    5. }
    6. printNum(n/10);
    7. System.out.print(n%10+" ");
    8. }
    9. public static void main(String[] args) {
    10. printNum(123);
    11. }

     运行结果:

    2、递归求 N 的阶乘 

    思路分析:对于阶乘有一个特点,N的阶乘为为N*(N-1)!,例如:5!=5*4! ,递归的出口便是1的阶乘为1。

    代码实现:

    1. public static int factorial(int n){
    2. if(n==1){
    3. return 1;
    4. }else{
    5. return n*factorial(n-1);
    6. }
    7. }
    8. public static void main(String[] args) {
    9. System.out.println(factorial(5));
    10. }

    运行结果: 

    3、返回的数字之和 

    题目描述: 输入一个非负整数,返回组成它的数字之和。

    思路分析:对于本题,需要求出各个位的数字,然后进行相加,由于与顺序无关,就可以对数字整除10,直至小于10,得到递归出口,然后是对数字取模相加。 

    代码实现: 

    1. public static int countNum(int num){
    2. if(num<10){
    3. return num;
    4. }else{
    5. return num%10+countNum(num/10);
    6. }
    7. }
    8. public static void main(String[] args) {
    9. System.out.println(countNum(125));
    10. }

    运行结果:

     

    三、汉诺塔问题 

    汉诺塔问题:该问题是在一块铜板装置上,有三根杆(编号A、B、C),在A杆自下而上、由大到小按顺序放置n个盘子。目标:把A杆上的金盘全部移到C杆上,并仍保持原有顺序叠好。操作规则:每次只能移动一个盘子,并且在移动过程中三根杆上都始终保持大盘在下,小盘在上,操作过程中盘子可以置于A、B、C任一杆上。 

     

    针对该问题可以先归纳:

    假设只有一个圆盘:直接A->C完成

    假设有两个圆盘:

    需要A->B,A->C,B->C  

    假设有三个圆盘:

     

    需要A->C ,A->B ,C->B, A->C ,B->A ,B->C, A->C  

    可以总结出规律:如果只有n==1,则直接 A->C,这就是递归出口,否则先将n-1个圆盘利用C,从A->B,然后再将最底层的圆盘从 A->C,然后再将剩余的n-1,利用A,从B->C。

    代码实现:

    1. public static void hunNuoTa(int n,char pos1,char pos2,char pos3){
    2. if(n==1){
    3. move(pos1,pos3);
    4. return;
    5. }
    6. hunNuoTa(n-1,pos1,pos3,pos2);
    7. move(pos1,pos3);
    8. hunNuoTa(n-1,pos2,pos1,pos3);
    9. }
    10. public static void move(char pos1,char pos2){
    11. System.out.print(pos1+"->"+pos2+" ");
    12. }
    13. public static void main(String[] args) {
    14. hunNuoTa(3,'A','B','C');
    15. }

    运行结果: 

     

     

     

     

     

  • 相关阅读:
    delphi 使用TFlowPanel容器,实现对内含控件进行自动排版
    崇州街子古镇中秋国庆热闹非凡
    Github操作—团队内协作(四)——Git
    专访 SPACE ID:通往 Web3 无许可域名服务协议之路
    Hadoop hdfs 常用命令
    鲜花线上销售管理系统的设计与实现
    consul服务注册与发现、服务配置与刷新
    【洛谷】P3378 【模板】堆
    【Arthas性能排查系列(一)】检查Java程序调用链路的耗时情况
    Android Studio(项目打包成APK)
  • 原文地址:https://blog.csdn.net/m0_62404808/article/details/127675333