这道上台阶的编程题你会不会?(递归和迭代思想)

面试题:

编程题:有n个台阶,一次只能上1步或者2步,共有多少种走法?

考察的知识点:

递归和循环迭代

递归:

n 的值

走法

算式

1

只能一次1步

f(1) = 1

2

(1)一次走1步<br />(2)直接走2步

f(2) = 2

3

(1)先到达f(1)的情况,再从f(1)直接跨2步<br />(2)先到达f(2)的情况,再从f(2)直接跨1步

f(3) = f(2) + f(1) = 3

4

(1)先到达f(2)的情况,再从f(2)直接跨2步<br />(2)先到达f(3)的情况,再从f(3)直接跨1步

f(4) = f(3) + f(2) = 5

...

...

...

n = x

(1)先到达f(n-2)的情况,再从f(n-2)直接跨2步<br />(2)先到达f(n-1)的情况,再从f(n-1)直接跨1步

f(x) = f(x - 2) + f( - 1)

递归方式的示例代码:

public class DiGuiTest {
    public static int diGui(int n) {
        if (n < 1) {
            throw new IllegalArgumentException(n + "不能小于1");
        }
        if (n == 1 || n == 2) {
            return n;
        }
        return diGui(n - 1) + diGui(n - 2);
    }

    public static void main(String[] args) {
        long start = System.currentTimeMillis();
        System.out.println(diGui(40)); // 165580141
        long end = System.currentTimeMillis();
        System.out.println("递归花费的时间:" + (end - start)); // 633ms
    }
}

循环迭代:

one保存最后走1步,two保存最后走2步。循环迭代就是不断修改这两个(one,two)变量的值。

n 的值

走法

算式

1

只能一次1步

f(1) = 1

2

(1)一次走1步<br />(2)直接走2步

f(2) = 2

3

(1)先到达f(1)的情况,再从f(1)直接跨2步<br />(2)先到达f(2)的情况,再从f(2)直接跨1步

f(3) = two + one<br />f(3) = f(1) + f(2)<br />two = f(2); one = f(1)

4

(1)先到达f(2)的情况,再从f(2)直接跨2步<br />(2)先到达f(3)的情况,再从f(3)直接跨1步

f(4) = two + one<br />f(4) = f(2) + f(3)<br />two = f(2); one = f(3)

...

...

...

n = x

(1)先到达f(n-2)的情况,再从f(n-2)直接跨2步<br />(2)先到达f(n-1)的情况,再从f(n-1)直接跨1步

f(x) = two + one<br />f(x) = f(x - 2) + f(x - 1)<br />two = f(x - 2); one = f(x - 1)

循环迭代方式的示例代码:

public class XunHunDieDaiTest {
    public static int xunHunDieDai(int n) {
        if (n < 1) {
            throw new IllegalArgumentException(n + "不能小于1");
        }
        if (n == 1 || n == 2) {
            return n;
        }
        int one = 1; // 初始化为走到第一级台阶的走法
        int two = 2; // 初始化为走到第二级台阶的走法
        int sum = 0;

        for (int i = 3; i <= n; i++) {
            sum = two + one;
            one = two;
            two = sum;
        }

        return sum;
    }

    public static void main(String[] args) {
        long start = System.currentTimeMillis();
        System.out.println(xunHunDieDai(40)); // 165580141
        long end = System.currentTimeMillis();
        System.out.println("循环迭代花费的时间:" + (end - start)); // < 1ms
    }
}

对比总结:

方法调用自身称之为递归,利用变量的原值推出新值称之为迭代。

递归:

  • 优点:大问题转化为小问题,可以减少代码量,同时代码更精简,可读性更好。
  • 缺点:递归调用浪费空间,而且递归太深容易造成堆栈溢出。

循环迭代:

  • 优点:代码运行效率好,因为时间只因循环次数增加而增加,而且没有额外的空间开销。
  • 缺点:代码不如递归简洁,可读性不是很好。

欢迎访问个人博客 https://wenshixin.gitee.io/blog/

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

扫码关注云+社区

领取腾讯云代金券