【Java学习】递归算法之斐波那契数列、100以内的阶乘

前言

今天介绍一下递归的使用，欢迎阅读~

正文

一、概述

1. 程序调用自身的编程技巧，称为递归。
2. 一个过程或函数在其定义或说明中有直接或间接调用自身的一种方法。

二、特点

1. 一个问题可被分解为若干层简单的子问题
2. 子问题和其上层问题的解决方案一致
3. 外层问题的解决依赖于子问题的解决

三、包含

1. 递归结束条件。（什么时候不调用自身方法。否则死循环）
2. 递归体。（什么时候需要调用自身方法）

四、优缺点

-优点

• 程序简单

-缺点

1. 递归调用时会占用大量的系统堆栈，内存耗用多。
2. 递归调用层次多时速度要比循环慢的多。

-应用

1. 任何可用递归解决的问题也能使用迭代解决；
2. 当递归方法可以更加自然地反映问题，并且易于理解和调试，并且不强调效率问题时，可以采用递归；
3. 在要求高性能的情况下尽量避免使用递归，既花时间又耗内存。

五、示例

1.斐波那契数列：

public class Fibonacci {
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        System.out.println("请输入要打印的斐波那契数列的个数：");
        int count =sc.nextInt();
        int x=1;
        int y=1;
        int z=0;
        for (int i = 1; i < count; i++) {
            if (i==1 || i==2){
                System.out.println(1+"	");
            }else{
                z=x+y;
                x=y;
                y=z;
                System.out.println(z+"	");
            }
        }
    }
}

2.100以内的阶乘

public class Factorial {
    public BigInteger sum(int i){
        if (i==1){
            return BigInteger.ONE;
        }
        return BigInteger.valueOf(i).multiply(sum(i-1));
    }

    public static void main(String[] args) {
        Factorial test =new Factorial();
        try{
            System.out.println("计算结果为："+test.sum(100)+"！");
        }catch (Exception e){
            e.printStackTrace();
        }
    }
}

☆ 3.求1~n的和（详解过程）

public class Example {
    public static void main(String[] args) {
        int sum = getSum(4);    //调用递归方法，获得1~4的和
        System.out.println("sum=" + sum);
    }
    public static int getSum(int n){
        if(n==1){
            return 1;
        }
        int temp = getSum(n-1);
        return temp + n;
    }
}

①方法包括参数和返回值。

如：(4-1)、（3-1）等是参数，return的是返回值。

②递归形成一个闭环，先执行等号右边的，全执行完之后（符合条件），（期间会保存下来方法的参数n）再执行等号右边的。

结尾

感谢阅读！欢迎小伙伴畅所欲言~