还在用递归，试试迭代吧

作者：爱笑的小雨

2022 年 3 月 08 日
本文字数：1815 字
阅读完需：约 6 分钟

递归 &迭代

递归（recursion）

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

迭代（iteration）

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

如题

有 n 步台阶，一次只能上 1 步或 2 步，共有多少种走法？

递归思路

n=1 ->一步 ->f(1)=1
n=2 ->（1）一步一步走（2）直接走 2 步 ->f(2)=2
n=3 ->（1）先到达第一级台阶（f(1)），然后直接跨两步（2）先到达第二级台阶（f(2)） ->f(3) = f(1) + f(2)
n=4 -> （1）先到达 f(2)，然后直接跨两步（2）先到达第二级台阶 f(3)，然后直接跨一步 ->f(4) = f(2) + f(3)
···
n=x （1）先到达 f(x-2)，然后直接跨两步（2）先到达第二级台阶 f(x-1)，然后直接跨一步 ->f(x) = f(x-2) + f(x-1)

循环迭代思路

n=1 ->一步 ->f(1)=1
n=2 ->（1）一步一步走（2）直接走 2 步 ->f(2)=2
n=3 ->（1）先到达第一级台阶（f(1)），然后直接跨两步（2）先到达第二级台阶（f(2)） ->f(3) = f(1) + f(2)
n=4 -> （1）先到达 f(2)，然后直接跨两步（2）先到达第二级台阶 f(3)，然后直接跨一步 ->f(4) = f(2) + f(3)
···
n=x （1）先到达 f(x-2)，然后直接跨两步（2）先到达第二级台阶 f(x-1)，然后直接跨一步 ->f(x) = f(x-2) + f(x-1)

从上面能看出不管有多少台阶，都要走到最后的 n-1 或 n-2 台阶的这两种情况，所以我们可以用两个临时变量 one=（f(n)-1）、two=（f(n)-2）保存这两个情况！

本题考点

递归
循环迭代

题解

递归方式

public class Recursion {
    public static void main(String[] args) {        long start = System.currentTimeMillis();        System.out.println(f(42));        long end = System.currentTimeMillis();        System.out.printf("耗时毫秒为：%d", end - start);    }
    /**     * 有n步台阶，一次只能上1步或2步，共有多少种走法的递归代码实现     * 性能损耗比较严重，特别是数据量大的时候，还会有可能造成栈溢出     *     * @param n 待计算的值     * @return 计算结果     */    public static int f(int n) {        if (n == 1 || n == 2) {            return n;        }        return f(n - 2) + f(n - 1);    }}

复制代码

循环迭代

public class LoopIteration {
    public static void main(String[] args) {        long start = System.currentTimeMillis();        System.out.println(loopIteration(42));        long end = System.currentTimeMillis();        System.out.printf("耗时毫秒为：%d", end - start);    }
    /**     * 循环迭代解决 有n步台阶，一次只能上1步或2步，共有多少种走法问题     *     * @param n 待计算的值（台阶数）     * @return 结果（多少种走法）     */    public static int loopIteration(int n) {        if (n < 1) {            throw new IllegalArgumentException(n + "不能小于1");        }        if (n == 1 || n == 2) {            return n;        }        // 当n=3，one=f(3-1)=f(2)=2,two=f(3-2)=f(1)=1        int one = 2; // 初始化走到最后需要走一步的走法        int two = 1; // 初始化走到最后需要走两步的走法        // 总步数        int sum = 0;        for (int i = 3; i <= n; i++) {            sum = one + two;            // 当i=4时，此时two=f(4-2)=f(2)=2，所以就是上一次的one            two = one;            // 当i=4时，one=f(4-1)=f(3)=3，所以就是上一次的sum            one = sum;        }        return sum;    }  }

复制代码

小结

对比以上两种方式的执行时间，能看出递归多耗时间了吧，所以能用迭代的地方千万不要使用递归
两种方式都是把大问题简化为小问题，从小问题一步一步推导出最终结果
理论上所有的递归和迭代可以相互转换，但实际从算法结构来说，递归声明的结构并不总能转换为迭代结构（原因有待研究）
方法调用自身称为递归，利用变量的原值推出新值称为迭代
递归
优点：大问题转化为小问题，可以减少代码量，同时代码精简，可读性好
缺点：递归调用浪费了空间，而且递归太深容易造成堆栈溢出
迭代
优点：代码运行效率好，因为时间只因循环次数增加而增加，而且没有额外的空间开销
缺点：代码不如递归简洁，可读性不太好（不易理解）

发布于: 刚刚阅读数: 2

原文链接:【http://xie.infoq.cn/article/99820cec893a85558e104c2be】。文章转载请联系作者。

爱笑的小雨

关注

公众号：爱笑的小雨 2020.12.19 加入

还未添加个人简介

发布

暂无评论

创作场景