递归算法案例——数列到函数

朱冰桂 改花

【摘要】递归算法是一种直接或者间接地调用自身的算法.在计算机编写程序中，递归算法对解决一大类问题是十分有效的，它往往使算法的描述简洁而且易于理解.递归过程一般通过函数或子过程来实现. 递归算法：在函数或子过程的内部，直接或者间接地调用自己的算法.本文通过具体的数学例子来体现这一基本思想，对第二个例子进行拓展，揭示了递推关系数列的函数实质.

【关键词】递归；递归算法；函数；数列

递归函数（recursive function）是一个自己调用自己的函数.递归函数包括两种：直接递归（direct recursion）和间接递归（indirect recursion）.直接递归是指函数F的代码中直接包含了调用F的语句，而间接递归是指函数F调用了函数G，G又调用了H，如此进行下去，直到F又被调用.

还有些数据结构如二叉树，结构本身固有递归特性；此外，有一类问题，其本身没有明显的递归结构，但用递归程序求解比其他方法更容易编写程序，如八皇后问题、汉诺塔问题等.

递归时常用的编程技术，其基本思想就是“自己调用自己”，一个使用递归技术的方法即是直接或间接地调用自身的方法.递归方法实际上体现了“以此类推”“用同样的步骤重复”这样的思想，它可以用简单的程序来解决某些复杂的计算问题，但是运算量较大.正因为递归程序的普遍性，我们应该学会使用递归来求解问题.在直接递归程序与间接递归中都要实现当前层调用下一层时的参数传递，取得下一层所返回的结果，并向上一层调用返回当前层的结果.至于各层调用中现场的保存与恢复，均由程序自动实现，不需要人工干预.因此，在递归程序的设计中关键是找出调用所需要的参数、返回的结果及递归调用结束的条件.如在阶乘函数Fact(n)中，各层要求传递一个自然数n，返回n*Fact(n-1)，递归调用结束的条件是n=0，据此，可以方便地写出它的对应程序

一、递归的基本思想

在中学学习数列知道，数列有用通项公式定义也有用递推式定义.

如an=2n；a0=a1=1，a2=2，n>2时，an=an-1+an-2.

同样的，表示函数可以用显式表达式、隐式方程、参数方程形式和递归式.

所谓递归就是自己调用自己，递归包含两种：直接递归和间接递归.

递归函数：用函数自身给出定义的函数，称为递归函数.

一般的递归函数可以用如下形式表达：a1=A，

an+1=f(n，an).

递归函数有两个要素：初始项、递推式.

与递归函数类似的说法，还有：

递归调用：在函数内部发出调用自身的操作.

递归方法：通过函数或过程调用自身将问题转换为本质相同但规模较小的子问题的方法.

递归算法：直接或者间接地调用自身的算法.

二、递归算法的基本思想

递归方法实际上体现了“以此类推”、“用同样的步骤重复”这样的思想，是算法和程序设计中的一种重要技术.

三、递归算法举例

例1已知s(n)=1+2+3+…+n=s(n-1)+n，当我们去求s(n)时，我们是先求出s(n-1)，然后再算出s(n)，具体语句为：s(n)=s(n-1)+n.

在这个语句中，我们调用s(n)求其值的时候，必须先调用s(n-1)得到其值，而要得到s(n-1)，又必须调用s(n-2)得到其值，同样，要求s(n-2)又要调用s(n-3)，依次类推，一直要递推到s(2)=s(1)+2，由于s（1）已知为1，所以可以得到s（2），从而得到s（3），这样一直可以得到s（n）.

这个递归算法中，自身调用的语句是：s（n）=s（n-1）+n，结束递归的边界条件是：s（1）=1.

例2数列f(n)满足f(n+1)=2+f(n)及f(1)=2，求这个数列的前五项.

解在递推公式f(n+1)=2+f(n)中，令n=1，可得f(2)=2+f(1)=2+2=2.

再令n=2，3，4，5，

可得f(5)=f(4)=f(3)=2+f(2)=2+2=2.

因此这个数列的前五项都是2.

注容易看出这个数列的各项都是2，即2，2，2，2，2，2，…

如果我们令f(1)=1，则可以求出该数列的前五项分别为：

f(2)=2+f(1)=3，

f(3)=2+f(2)=2+3，

f(4)=2+f(3)=2+2+3，

f(5)=2+f(4)=2+2+2+3.

可见，递归函数除了和相应的递推式有关外，不同的开始项，也会使结果有很大不同.

在上例中，如果我们修改递推式，改为f(n+1)=y+f(n)，且令f(1)=3，则当y=6时，我们可以得到f(5)=f(4)=f(3)=f(2)=6+f(1)=3，即数列的每一项都是3.

如果令f(1)=4，则当y=12时，我们可以得到f(5)=f(4)=f(3)=f(2)=6+f(1)=4，即数列的每一项都是4.

如果令f(1)=5，则当y=20时，我们可以得到f(5)=f(4)=f(3)=f(2)=6+f(1)=5，即数列的每一项都是5.

对以上各种情况我们列个表格，并设f(1)=x.

xyf(1)f(2)f(3)f(4)f(5)

2222222

3633333

41244444

52055555

63066666

可以发现当x，y满足一定的关系时，所得数列是常数列，即当y=x(x-1)时，数列为常数列.数列是自变量为自然数的函数这一思想得到体现.

如果我们把递推式改为f(n+1)=3y+f(n)且令f(1)=x2，我们可以得到当y=x2(x-1)时，数列是值为x的常数列.

综上所述，我们可以得到递归思想最终还是一种函数的思想，只不过在中学阶段接触到的是一些具体的数列例子，让同学们感到很是新鲜好奇.而在高等数学阶段，特别是对于计算机专业的学生，掌握递归思想意义重大，可以帮助他们创新，建立新模型，如果把数学中的函数思想很好地融入进去，可以拓展同学们的思路，降低问题的难度.

【参考文献】

王信峰.计算机数学基础.北京：高等教育出版社，2009.