台階走法遞歸

台階走法遞歸是一個經典的遞歸問題，在計算機演算法中有著廣泛的應用。本篇文章將從遞歸的思想出發，詳細分析如何解決這個問題。

一、遞歸基礎知識

遞歸是指一個函數直接或間接地調用自身。遞歸函數通常有兩個條件：遞歸終止條件和遞歸調用條件。在遞歸調用的過程中，每次都會將參數傳入一個新的函數中，這些新的函數形成一個遞歸調用的棧。當遞歸終止條件滿足時，逐層返回結果，直到回到最開始的函數。

遞歸函數可以方便地解決複雜問題，但是也容易導致時間和空間的浪費。因此，在編寫遞歸函數時需要特別注意終止條件和遞歸調用條件的設計。

二、問題描述

在一排有n個台階的樓梯上，每次可以向上邁1個或2個台階，問到達第n個台階有多少種走法。

三、解決方案

方法1：暴力遞歸

暴力遞歸即直接調用遞歸函數，計算所有可能的走法。由於存在大量重複計算，這種方法會導致時間複雜度為O(2^n)。

public static int countSteps(int n) {
    if (n == 1) {
        return 1;
    } else if (n == 2) {
        return 2;
    } else {
        return countSteps(n - 1) + countSteps(n - 2);
    }
}

方法2：遞歸加緩存

遞歸加緩存即使用一個數組來記錄每個n對應的走法數目，避免了大量重複的計算。這個方法的時間複雜度為O(n), 空間複雜度同樣為O(n)。

public static int countStepsWithCache(int n) {
    int[] cache = new int[n + 1];
    return countSteps(n, cache);
}

private static int countSteps(int n, int[] cache) {
    if (n == 1) {
        return 1;
    } else if (n == 2) {
        return 2;
    } else if (cache[n] > 0) {
        return cache[n];
    } else {
        int num = countSteps(n - 1, cache) + countSteps(n - 2, cache);
        cache[n] = num;
        return num;
    }
}

方法3：迭代法

迭代法即使用循環來計算結果。由於在計算過程中只需要用到前兩個結果，因此只需要使用兩個變數來保存結果。時間複雜度同樣為O(n)。

public static int countStepsWithLoop(int n) {
    if (n == 1) {
        return 1;
    } else if (n == 2) {
        return 2;
    } else {
        int a = 1, b = 2, c = 0;
        for (int i = 3; i <= n; i++) {
            c = a + b;
            a = b;
            b = c;
        }
        return c;
    }
}

四、總結

如上述，我們可以通過暴力遞歸、遞歸加緩存以及迭代法等方式來解決問題。在實際應用中，需要根據具體的問題來選擇合適的演算法。