Java数据结构-线性表之栈的应用-递归及其应用

ゞ浴缸里的玫瑰 2022-08-04 12:48 193阅读 0赞

递归函数的定义：把一个直接调用自己或通过一系列的调用语句间接地调用自己的函数，称做递归函数（递归函数必须有一个结束的条件，以免陷入无穷尽的递归中）。

迭代和递归的区别是：

(1).迭代使用的是循环结构，递归使用的是选择结构。

(2).递归能使程序的结构更清晰、更简洁、更容易让人理解，从而减少读懂代码的时间。但是大量的递归调用会建立函数的副本，会耗费大量的时间和内存。

(3).迭代则不需要反复调用函数和占用额外的内存。因此我们应该视不同情况选择不同的代码实现方式。

下面解释一下怎么使用栈实现递归：

在每次递归调用函数的时候，系统将函数的局部变量、参数值以及返回地址等信息压入栈中。在调用结束后，位于栈顶的信息(局部变量、参数值以及返回地址)就会被弹出，系统继续之前断点后面的代码。

下面是栈的其他应用，比如：

**汉诺塔问题**

汉诺塔：

汉诺塔（又称河内塔）问题是源于印度一个古老传说的益智玩具。大梵天创造世界的时候做了三根金刚石柱子，在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘。大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定，在小圆盘上不能放大圆盘，在三根柱子之间一次只能移动一个圆盘。

百度百科的解答：[点击查看详情][Link 1]

package example;
    public class Hanoi {
        /**
        * 
        * @param n 盘子的数目
        * @param origin 源座
        * @param assist 辅助座
        * @param destination 目的座
        */
        public void hanoi(int n, char origin, char assist, char destination) {
            if (n == 1) {
                move(origin, destination);
            } else {
                hanoi(n - 1, origin, destination, assist);
                move(origin, destination);
                hanoi(n - 1, assist, origin, destination);
            }
        }
    
        // Print the route of the movement
        private void move(char origin, char destination) {
            System.out.println("Direction:" + origin + "--->" + destination);
        }
    
        public static void main(String[] args) {
            Hanoi hanoi = new Hanoi();
            hanoi.hanoi(6, 'A', 'B', 'C');
        }
    }

**n的阶乘问题**

问题看似很简单，对于较小的数直接可以用简单的乘法运算求出来，但是当需要求的n比较大的时候，这个时候计算机运算就会出现越界问题了，从而没有办法求出n的阶乘。这里最要的问题就是大数运算了，而对于这种问题采用数组则可以很好的解决问题，如下是Java版的源代码实现。

public static BigInteger factorial(int n){
            int []a = new int[100];
            int i,j;
            int p,h;           //p存储当前结果的位数,h为进位
            a[0]=1;
            p=1;  
            for(i=2;i<=n;i++)   //循环与2,3,4.....n相乘
            {
                for(j=0,h=0;j<p;j++)    //让a[]的每位与i相乘
                {
                    a[j]=a[j]*i+h;
                    h=a[j]/10;
                    a[j]=a[j]%10;
                }
                while(h>0)         //如果h不为0
                {
                    a[j]=h%10;
                    h=h/10;
                    j++;
                }
                p=j;            //将当前的位数赋给p
            }
            StringBuffer sb = new StringBuffer();
            for(i=p-1;i>=0;i--)
            {
                sb.append(a[i]);
            }
            BigInteger bNum = new BigInteger(sb.toString());
            return bNum;
        }

[Link 1]: http://baike.baidu.com/link?url=Zs38-0LaSCDfvL7GEhu_LJ-U04n6seHMcuHvvAnBAJRHIm3BMjiRNlH0dqNlPZ65ncs4H7SNwHRmKKjiWG5ucK#4_4