首页 > 代码库 > java 中递归的实现 以及利用递归方法实现汉诺塔

java 中递归的实现 以及利用递归方法实现汉诺塔

2024-08-16 19:58:56   222人阅读

 今天说下java语言中比较常见的一种方法，递归方法。

递归的定义

简单来说递归的方法就是“自己调用自己”，通过递归方法往往可以将一个大问题简单化，最终压缩到一个易于处理的程度。对于编程来说，每次递归都会减少数据量；

java中递归的模式

每个递归函数的开头一定是判断递归结束条件是否满足的语句（一般是if语句）；函数体一定至少有一句是“自己调用自己”的。每个递归函数一定有一个控制递归可以终结的变量（通常是作为函数的参数而存在）。每次自己调用自己时，此变量会变化（一般是变小），并传送给被调用的函数。

下面是一个递归实现阶乘的简单程序

public static void main(String args[])
    {
         int n=8;
         int x;
         x=demo(n);
         System.out.println(x);
         
         
    }


public static int demo(int n)
{  int y;
   
    y=demo(n-1)*n;
    return y;
    }

}

 

该程序只能简单的实现已输入数字的递归，可以将上述的改为用户自己输入的形式去实现递归的结果；（有多中用户输入的方法暂时不涉及）

汉诺塔问题看似简单，却在思考上需要耗费大量的时间，如果不采用递归的方法的话，在实现上很难完成

题目大致是这样的：有三根相邻的柱子，标号为A,B,C，A柱子上从下到上按金字塔状叠放着n个不同大小的圆盘，要把所有盘子一个一个移动到柱子C上，并且每次移动同一根柱子上都不能出现大盘子在小盘子上方，请问至少需要多少次移动

接下来分析下这个问题

1.如果有A上有一个圆盘，直接将圆盘移到C上

2.如果有n个圆盘的话，则将前n-1个圆盘先移到B上，然后将自己移到，C上

所以这个问题可以分3步实现

1.将A上的n-1个圆盘借助C塔转移到B塔上

2把剩下的一个圆盘放到C上

3.将B上的n-1个圆盘借助A盘放到C盘上

以下是代码的实现

import javax.swing.JOptionPane;

public class Hannuo {
    public static void main(String args[])
    {
        String w=" ";
        w=JOptionPane.showInputDialog("please input panzishu");
        int j=0;
        char a=‘a‘,b=‘b‘,c=‘c‘;
        j=Integer.parseInt(w);
        move(j,a,b,c);
        
    }
    public static void move(int m,char a,char b,char c)
    {
        
        if(m==1)
        {
            JOptionPane.showMessageDialog(null,a+"->"+c," ",JOptionPane.PLAIN_MESSAGE);
        }
        else
        {
            move(m-1,a,c,b);
            JOptionPane.showMessageDialog(null,a+"->"+c," ",JOptionPane.PLAIN_MESSAGE);
            move(m-1,b,a,c);
        }
    }
    

}

 

java 中递归的实现 以及利用递归方法实现汉诺塔


联系
我们