scratch3.0少儿编程（虎薇科技Scratch3.0编程课程）

课程目标：通过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雪花就变成了一个面积有限但长度无限的图形，这非常有趣，递归算法能够非常好的解决此类复杂的带有自相似性的图形问题。

小结：可以看到，未来，随着计算力的算力越来越强，存储深度越来越大，递归理论将会在算法领域扮演举足轻重的作用。同学们应该理解这种算法的精髓，掌握这种算法的使用技巧，在编程和竞赛中能够很好的运用。

,