算法之 递归

--------递归在程序语言中简单的理解是：方法自己调用自己

一、简单递归

描叙

递归就是自己调用自己，不过需要注意的地方，需要给定跳出条件

代码示例

/**
 * 1、简单递归
 */
public class test1 {

    public static void main(String[] args) {
        fa(100);
    }


    public static void fa(int i) {
        if (i == 0) {
            return;
        }
        System.out.println(i);
        fa(i-1);
    }
}

二、三角数字递归

描叙

什么是三角数字
n个三角数字是 由 1+2+3…+n 所得值计算一个典型的三角数字。

• 1 的三角数字是1
• 2 的三角数字是 1+2 =3
• 3 的三角数字是 1 + 2 + 3 = 6
• 4 的三角数字是 1 + 2 + 3 + 4 = 10

下面通过代 计算 1+2+3…+n 所得值为多少

代码示例

package recursion;

/**
 * 2、三角数字递归
 * <p>
 * 首先大家应该知道什么是三角数字，三角数字的定义就是:
 * 滴n个三角数字是 由 1+。。。+n所得。
 * ........
 * 例如:
 * 1 的三角数字是1
 * 2 的三角数字是 1+2 =3
 * 3 的三角数字是 1 + 2 + 3 = 6
 * 4 的三角数字是 1 + 2 + 3 + 4 = 10
 * ..................................
 * 公式=   n= n+（ n-1） 
 */
public class test2 {

    public static void main(String[] args) {
        System.out.println("1 的三角数字是" + fa(1));
        System.out.println("2 的三角数字是" + fa(2));
        System.out.println("3 的三角数字是" + fa(3));
        System.out.println("4 的三角数字是" + fa(4));
    }


    /**
     * @param i
     */
    public static int fa(int i) {
        if (i == 1) {
            return 1;
        } else {
            return i + fa(i - 1);    // 4 +  3  + 2  +  1 （  1 是  (i == 1) 处的 1 ）
        }
    }

}

三、Fibonacci 树列递归 ( 斐波那契数列)

描叙

斐波那契数列就是典型的树列递归， 又名兔子数列 ,指的是这样一个数列：0，1、1、2、3、5、8、13、21、34、……

斐波那契数列（Fibonacci sequence），又称黄金分割数列、因数学家列昂纳多·斐波那契（Leonardoda Fibonacci）以兔子繁殖为例子而引入，故又称为“兔子数列”，指的是这样一个数列：1、1、2、3、5、8、13、21、34、……在数学上，斐波那契数列以如下被以递推的方法定义：F(1)=1，F(2)=1, F(n)=F(n - 1)+F(n - 2)（n ≥ 3，n ∈ N*）在现代物理、准晶体结构、化学等领域，斐波纳契数列都有直接的应用，为此，美国数学会从 1963 年起出版了以《斐波纳契数列季刊》为名的一份数学杂志，用于专门刊载这方面的研究成果。

代码示例

package recursion;

/**
 * 3、Fibonacci 树列递归 （斐波那契数列 = 兔子数列）,指的是这样一个数列：0，1、1、2、3、5、8、13、21、34、……在数学上，斐波纳契数列以如下被以递归的方法定义：F(1)=1，F(2)=1, F(n)=F(n-1)+F(n-2)（n>=2，n∈N*）。
 * <p>
 * 兔子问题,已知: 有一对刚出生的兔子,兔子从出生后的第三个月起开始每月生出一对小兔子,生成的小兔子第三个月起也开始每月生小兔子,假如兔子不会死,问20个月后兔子总数?
 * <p>
 * 第一月  1 (1)
 * 第二月  1
 * 第三月  2   一月生 1 对( 1+ 1 = 2)  --> 生出1对
 * 第四月  3   一月生 1 对( 2+ 1 = 3)  --> 生出1对
 * 第五月  5   一月生 1 对,三月生 1 对 ( 3 + 1+ 1 = 3)   --> 生出2对
 * 第六月  8   一月生 1 对,三月生 1 对,四月生 1 对  ( 5+1+1+1 = 8)   --> 生出3对
 * 第七月  13  一月生 1 对,三月生 1 对,四月生 1 对,五月生 2对  ( 8+ 1+1+1 +2 = 13)   --> 生出5对
 * </p>
 * 公式: 当前月数量 = 上1月 + 上2月 ， 出生数量= 上2月
 * <p>
 * F0 = 0; F1 = 1; Fn = Fn-1 + Fn-2
 */
 
public class test3 {
    public static void main(String[] args) {
        //rabbit();
        System.out.println(fib(24));
    }


    /**
     * 使用递归
     */
    public static int fib(int n) {
        if (n == 1 || n == 2) {
            return 1;
        } else {
            // 公式: 当前月数量 = 上1月 + 上2月 ,  System.out.println("第 " + n + "月出生" + num + "对, 总数量" + num + ",");
            return fib(n - 1) + fib(n - 2);
        }
    }


    /**
     * 使用循环
     */
    public static void rabbit() {
        System.out.println("第 1 个月兔子数 1 对");
        System.out.println("第 2 个月兔子数 1 对");
        int f1 = 1;
        int f2 = 1;
        int M = 24;
        int x;
        for (int i = 3; i <= M; i++) {
            x = f2;         // 上月总数
            f2 = f1 + f2;   // 本月总数 = 上月总数 + 上上月总数
            f1 = x;         // 把上月总数 定义成 下次循环的上上月总数
            System.out.println("第 " + i + " 个月兔子数 " + f2 + " 对");
        }
    }
}

本文到此结束，如果觉得有用，劳烦各位点赞关注一下呗，将不定时持续更新更多的内容…，感谢大家的观看！