递归和迭代的区别

红太狼 2023-10-01 10:21 2阅读 0赞

### 递归 ###

**递归（recursion）**：递归常被用来描述以自相似方法重复事物的过程，在数学和计算机科学中，指的是在函数定义中使用函数自身的方法。（如A调用A）

小时候听过这样一个故事：

从前有座山，山里有座庙，庙里有个老和尚，正在给小和尚讲故事；

从前有座山，山里有座庙，庙里有个老和尚，正在给小和尚讲故事…

这个故事没完没了，这就是递归的一种表现形式，只是由于故事没有结束条件，也就是递归无法结束，除非老和尚挂了。

还有个浅显易懂的例子：

假如你在电影院看电影，刚开始你没看票随便找了一个位置坐下去，然后再看是不是电影票上的那一排座位，然后你就问前面一排的人是在第几排，结果前面的人也不知道，于是前面的人继续向前问，直到问道第一排的时候，由于第一排前面没座位了，因此就回传给第二排，第二排告诉第三排，依次到你这一排就能知道到底是在第几排了。

### 迭代 ###

**迭代（iteration）**：重复反馈过程的活动，每一次迭代的结果会作为下一次迭代的初始值。（A重复调用B）

### 斐波拉契数列 ###

斐波那契数列指的是这样一个数列：

![image-20210913112547375][]

这个数列数列从第 3 项开始，每一项都等于前两项之和。其递推公式为：

F(0) = 0，F(1) = 1
    F(n) = F(n - 1) + F(n - 2)，其中 n > 1

#### 递归求解 ####

public int fib(int n) {
        
        if (n == 0) {
        
            return 0;
        }
        if (n == 1) {
        
            return 1;
        }
        return fib(n - 1) + fib(n - 2);
    }

#### 迭代求解 ####

public int fib(int n) {
        
        if (n == 0) return 0;
        if (n == 1 || n == 2) return 1;
        int a = 1;
        int b = 1;
        int temp = 0;//temp即为下一次循环的b的值
        for (int i = 3; i <= n; i++) {
        
            temp = a + b;
            a = b;
            b = temp;
        }
        return temp;
    }

[image-20210913112547375]: https://img-blog.csdnimg.cn/img_convert/063861c963bdd3553519ff8cdb79be87.png