「上次的遞迴題目，如果想通的話，那這次我們來試看看這一題」70. Climbing Stairs

「這題不是跟 509. Fibonacci Number 差不多嗎」兩人開始合作寫出

class Solution {
    fun climbStairs(n: Int): Int {
        return when {
            n == 0 -> 0
            n == 1 -> 1
            n == 2 -> 2
            else -> climbStairs(n-1) + climbStairs(n-2)
        }
    }
}

送出答案之後，第一次看到「Time Limit Exceeded」的兩人，開始面面相覷，不太知道該怎麼處理才好。

「對了！菁菁你上次教過我，可以看錯誤的資料是哪一筆」

Last executed input: 45

「沒錯！這一題的輸入比起之前的題目要大，所以之前的寫法沒法直接通過喔」夏天看了看兩人的解答之後說。

「如果要通過這一題，其中一個方法是放棄使用遞迴的寫法，改成使用迴圈」

class Solution {
    fun climbStairs(n: Int): Int {
        if (n <= 2) {
            return n
        }
        var result = 0
        var n1 = 1
        var n2 = 2
        (3..n).forEach { _ ->
            result = n1 + n2
            n1 = n2
            n2 = result
        }
        return result
    }
}

「原來迴圈也可以這樣寫！又學到一個新寫法囉」兩人驚訝的說。

「除了這個寫法之外，還可以使用一個叫做尾遞迴的概念。

尾遞迴簡單的說，就是遞迴的位置只有在整個函數的最尾端，呼叫函數自身。這樣的遞迴方式，可以讓編譯器做一些特殊處理，讓整個程式速度更快。

在 Kotlin 裡面，要宣告一個尾遞迴的函數，可以用 tailrec 這個關鍵字」

class Solution {
    fun climbStairs(n: Int): Int {
        return climbStairsRec(n, 1, 1)
    }

    private tailrec fun climbStairsRec(n: Int, first: Int, second: Int): Int {
        return when (n) {
            1 -> second
            else -> climbStairsRec(n - 1, second, first + second)
        }
    }
}

「哇⋯⋯這個我要想一下」曉欣拿出紙筆，開始思考這樣的遞迴為什麼會跟原本的方式有一樣的答案。

「沒問題，曉欣你這種拿出紙筆思考的習慣很好，很多工程師即便工作很長時間，都還是習慣嘗試用腦袋直接去想演算法。這樣的習慣其實很容易出錯。用紙筆不僅可以減少出錯的機會，同時也讓跟其他人的討論更加方便。」

「今天的觀念比較難一點點，就先讓兩位看看吧」