遞歸算法練習

當我們遇到復雜問題時，最好能通過分析理解題目找出簡單的方法來解決問題。今天我們一起來做一道Scratch競賽題——“爬臺階問題”。

小明要上二樓，從一樓到二樓共十級臺階。這次小明突然想到一個問題：“我上樓時一步可以爬一級臺階也可以跨兩級臺階，那么從一樓到二樓一共有多少種走法呢？”那么聰明的你可以幫小明用編程來解決這個問題嗎？

首先要分析題目：假設每次爬1級臺階需要10步，這種解法用數字化來表示為1、1、1……1。如果每次爬2級臺階則表示為2、2、2、2、2。當然我們還可以1級2級臺階交叉走……怎樣才能把所有可能性找出來呢？我們用編程的思路來解決，最簡單算法是多層嵌套循環，這是用最基礎的枚舉法。還可以想一想我們講過的遞歸算法，這種方法更加高效。

這道題要從后往前思考，假設小明只差最后一步就可以上第10級臺階了，這個時候只會出現兩種情況：第一種是只需要走1步（步長為1）從臺階9走到臺階10;第二種是需要走2步（步長為2）從臺階8走到臺階10。這樣最后一步就是從臺階9或者臺階8開始的，如果我從臺階0-8有X種辦法，從臺階0-9有Y種方法，那么從0-10級臺階有多少種解法呢？那么最后一步的走法數量就等于X+Y種。這樣得出結論：臺階0-10的走法等于臺階0-9的走法加臺階0-8的走法。依據這個結論繼續向前思考，臺階8的走法是臺階6+臺階7;臺階9的走法是臺階8+臺階7。這樣我們把這個復雜的問題就通過從后向前分段簡化了，這是一種特別有趣的解題技巧。依次往前推導，直到只剩1級或2級臺階。如果我們的數學水平足夠就可很直接地聯想到遞歸公式F（n）=F（n-1）+F（n-2），這個公式剛剛好可以用到這個題目中。（圖1）

有了數學公式再轉為編程代碼就簡單多了。我們這個程序更加通用，可以計算任意臺階數的方法數量，這樣需要詢問臺階總數。用變量“方法數”統計走法數量。（圖2）

在自定義積木模塊中，需要先判斷幾種特殊情況，當爬臺階數小于1時顯示“臺階數小于1，不符合題目要求”直接退出循環;當臺階數等于1時有1種走法;臺階數等于2時有2種走法（步長1或步長2）。下面就是利用遞歸算法不停調用自身。這樣就滿足公式F（n）=F（n-1）+F（n-2）。（圖3）

這樣程序就完成了。運行程序可以算出小明走10級臺階一共有89種方法。沒想到方法居然有這么多，不知道小明有沒有興趣把89種都走一遍。

下面問題升級了，可否把每一步的步長都列出來，保存在列表中，那么你該如何修改代碼呢？