遞歸函數初探

在編程學習中，大家常常會聽到一個詞語——遞歸。遞歸是什么？遞歸函數又是什么？一個過程或函數在其定義或說明中有直接或者間接調用自身的一種方法被稱為遞歸。

在經過一段時間的編程學習后你對遞歸函數一定不會陌生，我們經常需要用遞歸的方法來解決一系列復雜的問題，遞歸算法對于大多數問題都是很有效的，而且它很大程度上可以優化我們的代碼。今天我們結合Scratch和Python來講一講遞歸函數。

一、 Scratch算階乘

當我們想計算一個正整數的階乘時就可以應用到遞歸的思想。首先用戶手動輸入一個正整數，計算它的階乘。方法有兩種，一種使用循環的思路，不用遞歸（圖1）。一種創建一個自制積木，使用遞歸的思想（圖2）。

用循環計算階乘

用遞歸計算階乘

第一種方法直接按階乘的概念計算容易理解。利用循環的方法完成n！=1×2×3×4……n。

使用第二種遞歸方法對于初學者理解上有一點困難，首先需要創建一個帶變量的自制積木，然后在自制積木中增加遞歸的終止條件（如果n=1那么停止腳本程序），然后才能實施遞歸的過程，并且在自制積木中增加積木自身——完成調用自身，最終程序會根據遞歸的方法一直運行至終止條件才結束。

用Scratch的遞歸完成階乘計算后我們可以總結出以下三點：遞歸是在函數中調用函數本身;由于調用函數需要較多計算機資源，所以遞歸的效率比較低，如果有時間限制不建議使用;遞歸過程中需要有一個明確的結束條件，即遞歸出口。

二、 Python算階乘

如果在Python中遇到需要使用遞歸函數時，也需要在函數中調用函數本身。一定不要忘記增加停止的條件，如果不滿足條件就可以回到最外層調用的函數。

在學習遞歸函數時最經典的問題總是離不開斐波那契數列和漢諾塔。大家可以搜索相關的知識點，有很多利用遞歸方式來解決這些問題的例子。

同樣是階乘的問題給大家看看Python使用遞歸函數的解決方法（圖3）。

運行效果如圖4。

三、 藍橋杯中的遞歸問題

我們通過Scratch和Python的遞歸函數解決了階乘問題，接下來我們實戰一道藍橋杯中的遞歸題《母牛的故事》：有一頭母牛，它每年年初生一頭小母牛。每頭小母牛從第四個年頭開始，每年年初也生一頭小母牛。請編程實現在第n年的時候，共有多少頭母牛？

假設我們正在藍橋杯的賽場上，拿到題目之后首先需要分析題目，找出題中的規律：前四年牛的數量為母牛每年年初生一頭小母牛，小母牛是不生的。第五年開始小母牛也開始生子。根據這樣的規律我們可以列出如圖5的表格，這樣就更方便我們尋找其中規律了。從表格中可以得出公式：a[i]=a[i-1]+a[i-3]。

然后用我們學過的Python的知識，先定義列表，往list添加初始數據，預處理每年母牛的數量，輸入年份，輸出數量。

遞歸是學習編程中必須克服的一個難點，在今天有個初步了解后你可以查閱相關的資料完成斐波那契數列和漢諾塔的實例。