八. 遞歸

遞歸代碼模板：

def recursion(level, param1, param2, ...):
    # recursion terminator
    if level > MAX_LEVEL:
        print_result
        return
    # process logic in current level
    process_data(level, data...)
    # drill down
    self.recursion(level+1, p1, ...)
    # reverse the current level status if needed
    reverse_state(level)

118. 楊輝三角

題目：獲取楊輝三角的前幾行
輸入：numRows = 5
輸出： [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]

    def generate(self, numRows: int) -> List[List[int]]:
        if numRows == 0:
            return []
        if numRows == 1:
            return [[1]]

        if numRows > 1:
            res = self.generate(numRows-1) # 遞歸
            newlist = [1]
            for i in range(0, numRows-2):
                newlist.append(res[numRows-2][i]+res[numRows-2][i+1])
            newlist.append(1)
            res.append(newlist)
        return res

119. 楊輝三角 II

題目：獲取楊輝三角的某一行
輸入：rowIndex = 3
輸出：[1,3,3,1]

    def getRow(self, rowIndex: int) -> List[int]:
        if rowIndex == 0:
            return [1]
        if rowIndex == 1:
            return [1, 1]

        if rowIndex > 1:
            res = self.getRow(rowIndex-1)
            newlist = [1]
            for i in range(0, rowIndex-1):
                newlist.append(res[i]+res[i+1])
            newlist.append(1)
        return newlist