Intoweb

遞歸是學(xué)習(xí)編程中的一個(gè)難點(diǎn)，它的含義是：編程語言中，函數(shù)直接或間接調(diào)用函數(shù)本身，則該函數(shù)稱為遞歸函數(shù)。

換個(gè)通俗說法就是：從前有座山，山上有座廟，廟里有個(gè)老和尚給小和尚講故事，故事講的是：從前有座山……這樣講下去是不是沒有盡頭了，在實(shí)際編程中遞歸要設(shè)置一個(gè)遞歸出口，否則就成了死循環(huán)。

另外俄羅斯套娃也可以看作遞歸，娃娃里面套著娃娃……直到最小的娃娃（遞歸出口）。

初步了解了遞歸思想后，我們通過畫分形圖來體驗(yàn)一下遞歸的效果。

謝爾賓斯基三角形（Sierpinski triangle）是一個(gè)優(yōu)美的分形圖案。從一個(gè)大三角形開始，連接每一個(gè)邊的中點(diǎn)，將大三角形分為四個(gè)小三角形，然后挖掉中間的三角形，依次對(duì)其余三個(gè)三角形重復(fù)執(zhí)行上述操作，用Python繪制的效果如圖1，為了區(qū)分不同層級(jí)的三角形使用了不同的顏色。因?yàn)閷?duì)三角形不斷重復(fù)進(jìn)行分割操作，使用遞歸就能讓計(jì)算機(jī)畫出這個(gè)圖形了。

這是Scratch 繪制謝爾賓斯基三角形的代碼（如圖2）。由于遞歸函數(shù)需要引用本身，所以必須要用到自定義積木，這樣就可以在自定義積木中插入自身完成遞歸。

1. 自定義積木“謝爾賓斯基三角形（邊長）”。首先判斷如果邊長>4就繼續(xù)執(zhí)行，因?yàn)槔碚撋虾竺娴牟襟E2和3可以無限重復(fù)下去，就代碼而言，必須要保證算法的有窮性，通過設(shè)置邊長的最小值，程序就可以按需要終止。根據(jù)Scratch畫筆的精度，最小的三角形邊長大于4時(shí)，圖形效果較好。你可以自行試驗(yàn)最小邊長為3的效果，最小的三角形成實(shí)心的了。如圖3從左到右，不斷細(xì)分的謝爾賓斯基三角形（如圖3）。

2. 重復(fù)執(zhí)行3次，移動(dòng)“邊長”，左轉(zhuǎn)120度，畫出一個(gè)三角形。

3. 為了畫出更小一級(jí)的三角形，調(diào)用自身，并將邊長除以2。因?yàn)樵谥貜?fù)執(zhí)行3次的循環(huán)內(nèi)，所以可以畫出3個(gè)二分之一“邊長”的三角形。

4. 由于遞歸引用，所以三角形邊長會(huì)持續(xù)減半，實(shí)際執(zhí)行時(shí)設(shè)置邊長為200，會(huì)從最小邊長為6的三角形開始畫，逐漸畫出最大邊長200的三角形。實(shí)際繪制效果，如圖4。

通過繪制謝爾賓斯基三角形，我們初步接觸了在自定義積木中引用本身的結(jié)構(gòu)。這就是遞歸函數(shù)。遞歸概念是比較難以理解和用好的。未來我們將繼續(xù)對(duì)這個(gè)概念進(jìn)行更深入的學(xué)習(xí)。