算法之递归

淩亂°似流年 2023-02-14 01:50 19阅读 0赞

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

## 一、简单递归 ##

#### 描叙 ####

递归就是自己调用自己，不过需要注意的地方，需要给定跳出条件  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNDYzNjU1_size_16_color_FFFFFF_t_70]

#### 代码示例 ####

/**
     * 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、三角数字递归
 * 
 * 首先大家应该知道什么是三角数字，三角数字的定义就是:
 * 滴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*）。
 * 
 * 兔子问题,已知: 有一对刚出生的兔子,兔子从出生后的第三个月起开始每月生出一对小兔子,生成的小兔子第三个月起也开始每月生小兔子,假如兔子不会死,问20个月后兔子总数?
 * 
 * 第一月 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对
 * 
 * 公式: 当前月数量 = 上1月 + 上2月 ， 出生数量= 上2月
 * 
 * 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 + " 对");
 }
 }
 }

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

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNDYzNjU1_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200530175018370.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNDYzNjU1,size_16,color_FFFFFF,t_70