課程目标：通過Scratch3.0編程實現對遞歸原理的理解，同時對koch雪花的藝術實現有一個美學的認識。

年級：5-6年級

課時：4課時基礎

涉及領域：數學，藝術，編程

知識點：遞歸，階乘，漢諾塔，盜夢空間，斐波那契數列，分形

什麼是遞歸（Recursion）：

一個過程或函數在其定義或說明中有直接或間接調用自身的一種方法被稱為遞歸，遞歸做為一種算法在程序設計語言中廣泛應用。這麼說是不是太太太抽象了呢？簡單的說就是一段程序自己調用自己，調用的意思就是使用，讓我們舉幾個實際的例子：

整數的階乘（Factorial）：

一個正整數的階乘是所有小于及等于該數的正整數的積，并且0的階乘為1。自然數n的階乘寫作n!。即n!=1×2×3×...×n。階乘是可以用遞歸方式定義：0!=1，n!=(n-1)!×n。n的階乘等于n乘以n-1的階乘，如果把計算n的階乘定義為一個函數，那麼在這個函數裡會再次調用自己去求n-1的階乘，在計算n-1階乘的函數裡，會再次調用自己去求n-2的階乘，如此往複，直到達到限制條件n=0，遞歸終止，程序會帶着1！= 1這個計算結果一層一層的返回計算，最後算出n！。

整數的階乘

從前有座山：

從前有座山，山上有座廟，廟裡有個老和尚給小和尚講故事。講的那是：

從前有座山，山上有座廟，廟裡有個老和尚給小和尚講故事。講的那是：

從前有座山，山上有座廟，廟裡有個老和尚給小和尚講故事。講的那是：從前有座山……

這個故事就是一個遞歸函數，而且沒有設置限制條件，這個一個永遠也講不完的故事。

從前有座山

斐波那契數列（Fibonacci sequence）

又稱黃金分割數列，因數學家列昂納多·斐波那契（Leonardoda Fibonacci）以兔子繁殖為例子而引入，故又稱為“兔子數列”，指的是這樣一個數列：1、1、2、3、5、8、13、21、34、55、89、144……在數學上，斐波納契數列以如下方法定義：F(1)=1，F(2)=1, F(n)=F(n-1) F(n-2)（n>=3，n∈N*）。這個數列從第3項開始，每一項都等于前兩項之和。在現代物理、準晶體結構、生物，化學、金融經濟等領域，斐波納契數列都有直接的應用。

斐波那契螺旋線，又稱黃金螺旋線

盜夢空間（Inception）：

電影裡面的夢境層次用到了編程中的遞歸的概念。影片中四次使用盜夢機，而且每次使用都是在上一層夢境的基礎上進行使用，從編程的視角上看，造夢機就是遞歸函數，夢中夢就是遞歸夢。

盜夢空間的夢境層次

設計一個造夢機函數叫Inception()；

1、現實層：飛機上，程序中第一次調用Inception()，進入下一層；

2、夢境第一層：面包車，第二次調用Inception()，進入下一層；

3、夢境第二層：酒店，第三次調用Inception()，進入下一層：

4、夢境第三層：雪地森林，第四次調用Inception()，進入下一層

5、夢境第四層：潛意識邊緣，完成任務，返回上一層（return一次）；

6、夢境第三層：植入意識mind，完成任務。直接一二三層同步kick回現實層（相當于連續return三次）

7、現實層，程序繼續運行。

漢諾塔（Hanoi Tower）：

漢諾塔源于印度一個古老傳說。大梵天創造世界的時候做了三根金剛石柱子，在一根柱子上從下往上按照大小順序摞着64片黃金圓盤。大梵天命令婆羅門把圓盤從下面開始按大小順序重新擺放在另一根柱子上。并且規定，在小圓盤上不能放大圓盤，在三根柱子之間一次隻能移動一個圓盤。僧侶們預言，當所有的金片都從梵天穿好的那根針上移到另外一根針上時，世界就将在一聲霹靂中消滅，而梵塔、廟宇和衆生也都将同歸于盡。

8層漢諾塔

分形(Fractal):

分形，被定義為一個幾何形狀，可以分成數個部分，且每一部分都（至少近似地）是整體縮小後的形狀”，即具有自相似的性質。最常見的分形就是koch雪花，海岸線等。分形理論在很多領域都得到了充分的應用，被稱為是科學與藝術的完美結合。

koch雪花的分形規則

下面我們用scratch3.0解決幾個實際的遞歸問題：

1、用遞歸算法計算n的階乘

計算階乘的積木

計算得出5的階乘是120。10的階乘是3628800

2、用遞歸算法計算斐波那契數列：

計算斐波那契數列的第n個數的積木

斐波那契數列的第15個數是610

3、用遞歸算法計算漢諾塔：

漢諾塔

a柱：起始柱，b柱：輔助柱，c柱：目标柱

這個問題我們從後往前推，假設此時經過不懈的努力，我們已經把n-1個盤子移到附屬柱b柱了，把最大的盤子由a柱移到c柱後，b柱上是餘下的63個盤子，a為空。因此現在的目标就變成了将這63個盤子由b移到c。這個問題和原來的問題完全一樣，隻是由a柱換為了b柱，數量由64變為了63。因此可以采用相同的方法，先将上面的62個盤子由b移到a，再将最下面的盤子移到c……

因此我們設計一個移動n個盤子到a、b、c柱子的函數

f（n，a，b，c）：

step1 将n-1個盤子由a到b

step2 将第n個盤子移動到c

step3 将n-1個盤子由b到c

這個函數的第一步就是調用自己，把n改成n-1，把c改成b

第三步也是調用自己，把n改成n-1，把a改成b

Scratch3.0中制作一個可以移動n個盤子到a、b、c柱子的積木（函數）

5層漢諾塔

4、用遞歸算法繪制經典分形--koch雪花：

定義一個繪制koch雪花的遞歸函數

0級koch雪花

1級koch雪花

3級koch雪花

4級koch雪花

5級koch雪花

當級數變得無窮大時，koch雪花就變成了一個面積有限但長度無限的圖形，這非常有趣，遞歸算法能夠非常好的解決此類複雜的帶有自相似性的圖形問題。

小結：可以看到，未來，随着計算力的算力越來越強，存儲深度越來越大，遞歸理論将會在算法領域扮演舉足輕重的作用。同學們應該理解這種算法的精髓，掌握這種算法的使用技巧，在編程和競賽中能夠很好的運用。