面試題：

編程題：有n個(gè)臺(tái)階，一次只能上1步或者2步，共有多少種走法？

考察的知識(shí)點(diǎn)：

遞歸和循環(huán)迭代

遞歸：

遞歸方式的示例代碼：

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("遞歸花費(fèi)的時(shí)間：" + (end - start)); // 633ms
    }
}

循環(huán)迭代：

one保存最后走1步，two保存最后走2步。循環(huán)迭代就是不斷修改這兩個(gè)（one，two）變量的值。

循環(huán)迭代方式的示例代碼：

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; // 初始化為走到第一級(jí)臺(tái)階的走法
        int two = 2; // 初始化為走到第二級(jí)臺(tái)階的走法
        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("循環(huán)迭代花費(fèi)的時(shí)間：" + (end - start)); // < 1ms
    }
}

對(duì)比總結(jié)：

方法調(diào)用自身稱之為遞歸，利用變量的原值推出新值稱之為迭代。

遞歸：

• 優(yōu)點(diǎn)：大問題轉(zhuǎn)化為小問題，可以減少代碼量，同時(shí)代碼更精簡(jiǎn)，可讀性更好。
• 缺點(diǎn)：遞歸調(diào)用浪費(fèi)空間，而且遞歸太深容易造成堆棧溢出。

循環(huán)迭代：

• 優(yōu)點(diǎn)：代碼運(yùn)行效率好，因?yàn)闀r(shí)間只因循環(huán)次數(shù)增加而增加，而且沒有額外的空間開銷。
• 缺點(diǎn)：代碼不如遞歸簡(jiǎn)潔，可讀性不是很好。

歡迎訪問個(gè)人博客 https://wenshixin.gitee.io/blog/