递归函数初探

在编程学习中，大家常常会听到一个词语——递归。递歸是什么？递归函数又是什么？一个过程或函数在其定义或说明中有直接或者间接调用自身的一种方法被称为递归。

在经过一段时间的编程学习后你对递归函数一定不会陌生，我们经常需要用递归的方法来解决一系列复杂的问题，递归算法对于大多数问题都是很有效的，而且它很大程度上可以优化我们的代码。今天我们结合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添加初始数据，预处理每年母牛的数量，输入年份，输出数量。

递归是学习编程中必须克服的一个难点，在今天有个初步了解后你可以查阅相关的资料完成斐波那契数列和汉诺塔的实例。