YuanbaoQiang
0%

递归算法实例（持续更新...）

Posted on Edited on In Valine:
Symbols count in article: 1.5k Reading time ≈ 1 mins.

递归——迭代是人，递归是神🙆‍♂️

To Iterate is Human, to Recurse, Divine. ——— L. Peter Deutsch

递归是指在函数的定义中使用函数自身的方法，递归一定要向已知方向递归，否则这种递归就变成了无穷递归，类似于死循环。

目前刚接触递归，但是已经感觉它的难度了…后续持续补充相关算法，加深理解😜。

1-n之和

1
2
3
4
5
6
7
8
9
10
11
12
13
14
/**
 * @description: 1-n 之和
 * @author: YuanbaoQiang
 * @date: 2020/7/26 20:02
 * @param n
 * @return: int
 */
public int getSum(int n){
    if(n == 1){
        return 1;
    }else{
        return n + getSum(n-1);
    }
}

n！

1
2
3
4
5
6
7
public int getProduct(int n){
    if(n == 1){
        return 1;
    }else{
        return n * getProduct(n-1);
    }
}

斐波那契数列（Fibonacci sequence）

表达式：F(1)=1，F(2)=1, F(n)=F(n - 1)+F(n - 2)（n ≥ 3，n ∈ N*）

0、1、1、2、3、5、8、13、21、34、……

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/**
 * @description: 斐波那契数列：1、1、2、3、5、8、13、21、34、……
 * @author: YuanbaoQiang
 * @date: 2020/7/26 20:15
 * @param n
 * @return: int
 */
public int getFibonacci(int n){
    if(n == 1 ){
        return 1;
    }else if(n == 2){
        return 1;
    }else{
        return getFibonacci(n-1) + getFibonacci(n-2);
    }
}

汉诺塔问题

有三根杆子A，B，C。A杆上有 N 个 (N>1) 穿孔圆盘，盘的尺寸由下到上依次变小。要求按下列规则将所有圆盘移至 C 杆：

  1. 每次只能移动一个圆盘；
  2. 大盘不能叠在小盘上面。

三层

四层

十层

……

个人理解

其实整个过程主要是三个主要流程:

  1. 将n-1个圆盘从A转移到B；（A—>B）
  2. 将最大的圆盘从A转移到C；（A—>C）
  3. 此时的B上的n-1个圆盘和初始状态的A是一样的，再次进行1-2步骤。（B—>C）

例如以下的例子，可以将63个圆盘堪称一个整体，依次类推。

代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/**
 * @description: 汉诺塔问题
 * @author: YuanbaoQiang
 * @date: 2020/7/26 20:40
 * @param num
 * @param A
 * @param B
 * @param C
 * @return: void
 */
public void hanNuo(int num, char A, char B, char C){
    if(num == 1){
        System.out.println(A + "-->" + C);
    }else{
        hanNuo(num-1, A, C, B); // 将num-1个圆盘从A转移到B
        System.out.println(A + "-->" + C);
        hanNuo(num-1, B, A, C); // 将num-1个圆盘从B转移到C
    }
}