下载文档原格式
递归算法案例【摘要】递归算法是一种直接或者间接地调用自身的算法.在计算机编写程序中，递归算法对解决一大类问题是十分有效的，它往往使算法的描述简洁而且易于理解.递归过程一般通过函数或子过程来实现. 递归算法：在函数或子过程的内部，直接或者间接地调用自己的算法.本文通过具体的数学例子来体现这一基本思想，对第二个例子进行拓展，揭示了递推关系数列的函数实质.【关键词】递归；递归算法；函数；数列递归函数（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)22222223633333412444445205555563066666可以发现当x，y满足一定的关系时，所得数列是常数列，即当y=x(x-1)时，数列为常数列.数列是自变量为自然数的函数这一思想得到体现.如果我们把递推式改为f(n+1)=3y+f(n)且令f(1)=x2，我们可以得到当y=x2(x-1)时，数列是值为x的常数列.综上所述，我们可以得到递归思想最终还是一种函数的思想，只不过在中学阶段接触到的是一些具体的数列例子，让同学们感到很是新鲜好奇.而在高等数学阶段，特别是对于计算机专业的学生，掌握递归思想意义重大，可以帮助他们创新，建立新模型，如果把数学中的函数思想很好地融入进去，可以拓展同学们的思路，降低问题的难度.【参考文献】王信峰.计算机数学基础.北京：高等教育出版社，2009.。
数据结构论文——递归算法的讨论所谓递归算法是把问题转化为规模缩小了的同类问题的子问题。
然后递归调用函数（或过程）来表示问题的解。
一个过程(或函数)直接或间接调用自己本身,这种过程(或函数)叫递归过程(或函数)。
递归过程一般通过函数或子过程来实现。
递归方法：在函数或子过程的内部，直接或者间接地调用自己的算法。
递归算法是一种直接或者间接地调用自身算法的过程。
在计算机编写程序中，递归算法对解决一大类问题是十分有效的，它往往使算法的描述简洁而且易于理解。
递归算法解决问题的特点：(1) 递归就是在过程或函数里调用自身。
(2) 在使用递归策略时，必须有一个明确的递归结束条件，称为递归出口。
(3) 递归算法解题通常显得很简洁，但递归算法解题的运行效率较低。
(4) 在递归调用的过程当中系统为每一层的返回点、局部量等开辟了栈来存储。
递归次数过多容易造成栈溢出等。
所以一般不提倡用递归算法设计程序。
下面就让我们结合例子详细讨论一下递归算法。
一、递归算法的原理递归算法简单的说就是在函数中调用函数自身，不断调用，直到满足函数得出计算结果(某个条件)。
因为其需要不断循环的调用自身，所以称为递归调用。
递归的原理,其实就是一个栈(stack), 比如求5的阶乘,要知道5的阶乘,就要知道4的阶乘,4又要是到3的,以此类推,所以递归式就先把5的阶乘表示入栈, 在把4的入栈,直到最后一个,之后呢在从1开始出栈, 看起来很麻烦,确实很麻烦,他的好处就是写起代码来,十分的快,而且代码简洁,其他就没什么好处了,运行效率出奇的慢。
还有一个十分形象的例子：从前有座山，山里有个庙，庙里有个老和尚正在讲故事：从前有座山，山里有个庙，庙里有个老和尚正在讲故事：从前有座山，山里有个庙，庙里有个老和尚正在讲故事……如此循环往复到最终的要求。
递归分为2种，直接递归和间接递归。
直接递归，比如方法A内部调用方法A自身。
间接递归，比如方法A内部调用方法B，方法B内部调用方法C，方法C 内部调用方法A。
《用递归法解决问题》教学设计学习者分析本节课的教学对象为高中二年级的学生。
这个阶段的学生具有很强的自主意识，具备一定的探究能力，喜欢自己动手实践来获得新知。
多次经历从问题到程序的思考过程，在面对现有软件无法解决的问题时能够编写程序解决问题。
在此之前，学生已经掌握了循环、数组、自定义函数的使用，为本课的学习做好了充分的准备。
学习内容分析《用递归法解决问题》是高中选修教材《算法与程序设计》（科教版）第三章“算法的程序实现”第五小节的内容。
在本课学习之前，学生已经学会了用循环的方法来解决问题，然而循环的方法往往并不会那么清晰地描述解决问题的步骤，递归法则可以非常直白地描述一个问题的求解过程，因此递归法也是最容易实现的算法。
递归的基本思想是把规模大的问题转化为规模小的相类似的子问题来解决。
在函数实现时，因为解决大问题的方法和解决小问题的方法往往是同一种方法，所以就产生了调用自身的情况。
递归是利用系统的堆栈保存函数中的局部变量来解决问题的，因为函数调用的开销比较大，递归常常会带来效率问题。
本节课学生不仅要学会用递归法解决问题，更重要的是领会递归思想的精髓。
递归思想是计算机学科中的核心技术思想之一，其本质反映的是一种将复杂问题简单化的思维方法。
学习目标知识与技能目标：理解递归的含义，找出递归问题中缩小问题规模的递归处理方法及递归结束条件，了解递归算法的优缺点。
过程与方法目标：能用程序实现递归算法，学会用简单模式解决复杂问题的方法。
情感态度与价值观目标：领悟递归思想，体验递归思想在实际生活中的应用。
教学重点、难点重点：分析递归结束条件及缩小问题规模的方法，以及递归算法的程序实现。
难点：递归算法的程序实现。
教学策略呈现斐波那契数列问题，由学生比较熟悉的递推法入手，针对问题描述中的不严谨之处，引入递归定义及其关键因素――递归结束条件和缩小问题规模的递归处理。
在递归的学习过程中，学生通过阅读代码、尝试模仿、归纳提炼、拓展应用等环节逐渐完成知识的内化并达到应用、迁移的目的。
递归算法及经典例题详解大部分人在学习编程时接触的第一个算法应该就是递归了，递归的思想其实很好理解，就是将一个问题拆分为若干个与本身相似的子问题，通过不断调用自身来求解。
但很多新手在实际操作中却很难正确使用到递归，有时面对问题还会有种无从下手的感觉，在此，我总结了一些解决递归问题的方法和思路，希望对你能有所帮助。
1.什么是递归递归简单来说就是在运行过程中不断调用自己，直到碰到终止条件，返回结果的过程。
递归可以看作两个过程，分别是递和归。
递就是原问题把要计算的结果传给子问题；归则是子问题求出结果后，把结果层层返回原问题的过程。
下面设一个需要经过三次递归的问题，为大家详细看一下递归的过程：当然，现实中我们遇到递归问题是不会按照图中一样一步一步想下来，主要还是要掌握递归的思想，找到每个问题中的规律。
2.什么时候使用递归递归算法无外乎就是以下三点：1.大问题可以拆分为若干小问题2.原问题与子问题除数据规模不同，求解思路完全相同3.存在递归终止条件而在实际面对递归问题时，我们还需要考虑第四点：当不满足终止条件时，要如何缩小函数值并让其进入下一层循环中3.递归的实际运用（阶层计算）了解了大概的思路，现在就要开始实战了。
下面我们来看一道经典例题：求N的阶层。
首先按照思路分析是否可以使用递归算法：1.N！可以拆分为（N-1）！*N2.（N-1）！与N！只有数字规模不同，求解思路相同3.当N=1时，结果为1，递归终止满足条件，可以递归：public static int Factorial(int num){if(num==1){return num;}return num*Factorial(num-1);}而最后的return，便是第四步，缩小参数num的值，让递归进入下一层。
一般来说，第四步往往是最难的，需要弄清该如何缩小范围，如何操作返回的数值，这一步只能通过不断地练习提高了（当然如果你知道问题的数学规律也是可以试出来的）。
- 66 -
前言
1 在计算机程序设计中，采用高效而简洁的算法可以提高程序的稳定性和可读性，不同的算法中蕴涵着不同的数学思想，将数学思想融入到算法构造以及程序设计中是十分重要的．
本文所探讨的递归算法，即一种直接或者间接调用自身的方法，许多数学表达式都可以用递归的方法来定义，典型的就是数列，我们可以通过通项公式来求解任意一项．递归算法
2 递归的背景：数学归纳法
2.1 首先，用数学归纳法简单说明如下定理的成立．定理1 对于任意整数前≥，前个整数的和N 1N 1+…值为．
2+3++N N(N+1)/2显然，该定理对是成立的．进一步检查发现对于N=1≤≤结论都是正确的．然而对于定理需要进行证2N 10明．首先，需要证明定理的最小情况是正确的，然后再证明如果最初的几种情况是正确的，就能将其扩展到接下来的情况．如一个定理若对于≤≤是正确的，我们就1N k 要证明该定理对于≤≤一定是正确的．一旦给出1N k+1了如何扩展正确情况的范围，就证明了该定理对于所有的情况都是正确的．
定理可以通过如下程序段来实现（）：1C++自然数列前项求和公式// N public static long s(int n){if(n==1)
return 1;
else
return s(n-1)+n;}
由以上程序段可以看出，函数是在调用自身的副本s 来完成求和的计算，就是采用的递归算法．递归算法的基本问题
2.2 斐波那契数列（）
Fibonacci 假定一对刚出生的小兔一个月后就能长成大兔，再过一个月便能生下一对小兔，并且此后每个月都生一对小兔．一年内没有发生死亡．问一对刚出生的兔子，一年内能繁殖成多少对兔子？
逐月推算，我们可以得到数列：，，，，，，112358，，，，，，，……数列中的每一项，1321345589144233则称为“斐波那契数”．第十三位的斐波那契数，即为一对刚出生的小兔，一年内所能繁殖成的兔子的对数．从斐
从递归算法看数学在计算机程序设计方面的应用
马良斋
（兰州交通大学，甘肃兰州）
730070摘要： 随着计算机技术的快速发展，数学知识在计算机技术发展中，尤其是在计算机应用程序设计中处于及其重要的地位．同时，用数学的思维解决各种程序设计方面的难题也是十分重要的．在程序设计当中所解决的相当一部分问题都会涉及到各种各样的科学计算，这需要程序员将实际问题转换为程序，要经过对问题抽象的过程，建立起完善的数学模型，才能设计出好的软件．文章将介绍递归算法在程序设计中的应用并探讨数学知识在程序设计中应用及其重要性．
关键词：应用程序；递归算法；程序设计
中图分类号：文献标识码：文章编号：－（）－－TP312 A 16720520200705006602
———————————————收稿日期：2007-6-30
作者简介：马良斋（—），男，回族，兰州市人，兰州交通大学电子与信息工程学院教师，主要从事计算机基础的教1978学与研究工作．
第卷第期（）河西学院学报（）
2352007 Vol.23 No.52007“兔子”问题图解
- 67 -
波那契数的构造明显看出斐波那契数列从第三项起，每项都等于前面两项的和．假定第项斐波那契数为，于是n Fn 我们有：
由以上的函数表达式我们可以看到该数列的求解就是一个递归的过程．其递归基础就是和的值，存在着F1F2不使用递归就可以解决问题的情况，即前文所说的归纳基础．该数列的向前进展情况便是其递归调用向归纳基础方向进展，即Fn+1=Fn+Fn-1≥．由此我们可以得到递归(n 2)函数的两条基本的递归原则，即递归基础和向前进展．
以上这种数学思想在计算机的程序设计方面有很重要的作用，利用递归调用程序设计可以解决很复杂但规律性很强的问题，并且可以使程序变得简洁易懂．递归所带来的问题
2.3 递归方法其虽然有强大的功能．然而，递归的思想在程序设计中并不总是最合适的算法．我们知道斐波那契数列是递归定义的，写一个计算斐波那契数的程序也是很容易的，但是如果该程序可以运行，则存在一个很严重的问题，例如我们要计算，即使在相对较快的计算机上运F40行也需要分多钟，该基本计算就需要次的加法，这139个时间花费实在太大．
根本问题在于递归进行了太多的多余计算，如果要计算，则需要计算，依次类推需要计算，Fn Fn-1Fn-2Fn-3等等，会多次调用先前已经调用的计算结果，即每一次递归都会做越来越多的计算．在从算法的时空复杂度上来说，递归的效率甚至比不上循环算法的效率．这样的情况下应了解使用递归的又一原则：不应使用单独的递归调用来处理类似的问题而是问题复杂化．
由此可见，评价一个算法的优劣，不仅要从程序的可读性，简洁性以及健壮性，重要的要看算法所需的时间复杂度．
数学在计算机程序设计方面的应用
3 起初，计算机科学只是数学的一个分支，随着时代的发展，人们越来越理解计算机与数学是密不可分的．计算机事实上是一个计算工具，而数学问题并不仅仅是依靠计算来解决的．所以想只依靠计算机的强大计算功能来解决问题是不现实的，计算机已经越来越深入到思维领域．例如世界难题四色问题就是被计算机证明的．问题的求解过程许多具有实用价值的数学分支如分析几何、小波分析、离散数学、仿生计算、数值计算中的有限单元方法等等的发明者可以说就是在该图的刺激下潜移默化地感悟到发现的方向．计算机科学的数学理论体系是相当庞杂的，参考了计算机科学理论的的学科体系，涉及的问题主要有数值计算、离散数学、数论以及计算理论这几个方向．计算机
科学的发展有赖于硬件技术和软件技术的综合．在设计硬件的时候应当充分融入软件的设计思想，才能使硬件在程序的指挥下发挥极致的性能．在软件设计的时候也要充分考虑硬件的特点，才能冲破软件效率的瓶颈．达到硬件和软件设计的统一，一般的程序设计者很难将这样的思想贯穿在其程序设计当中．仅举个简单的例子，我们在写一些语言的程序，必要的时候都会采取内嵌一段汇编指令，C 这就是比较充分地考虑了硬件的工作情况，从而能够提高程序运行的效率．所以我们也有必要了解一些硬件的基础知识．
从事计算机硬件程序设计的程序员，则不可回避的就是数字信号处理．这门科学所用到的数学基础主要有三角函数、微积分、高次方程求解、数值逼近，傅里叶变换等．在滤波器的设计当中还会用到矩阵运算．一位计算机开发者曾经研究过一个VC 环境下开发的滤波器的++模拟软件，就是利用莱文逊杜宾递推算法，在较大规模-的矩阵运算基础上进行的．当然，开发的环境不一定是这个，可以选择或者纯语言编译器．如果我们MATLAB C 不了解相关的数学基础，不要说程序设计，就算是建立运算模型都是相当困难的．
由此可见，在计算机程序设计中，数学知识扮演着及其重要的角色，用数学思想来解决在程序设计当中所解决的相当一部分问题都会涉及到各种各样的科学计算，这需要程序员将实际问题转换为程序，要经过对问题抽象的过程，建立起完善的数学模型．总结
4 对于一个抽象的数学问题，当需要使用计算机以及不同算法解决时，需要先将抽象问题模型化，即所说的数学建模，数学中除了一些基本概念是从现实世界通过一般抽象得来的以外，大部分概念是通过定义的方式（可能通过某种类比）逻辑建构起来的，就如所说递归问题便是如此，它有其递归基础和向前发展趋势，这点是十分重要的，不会使得递归无限循环下去．该思想纯数学研究中更显得突出，如环→理想→商环的逐步抽象．
作为一名学习计算机的老师，需要了解的是，研究问题的精力是有限的，可以对上面的方方面面都有所涉及，以体会数学这个强大的理论工具，为今后的工作奠定一个坚实的基础．在计算机的程序设计中，灵活运用的数学知识将抽象的问题模型化是十分重要的．参考文献：
中国计算机学会．计算机科学技术百科全书．北京：清华[1][M]大学出版社，．
2001同济大学数学教研室．工程数学－线性代数．上海：同济[2][M]大学出版社，．
1999李庆阳．数值分析．武汉：华中科技大学出版社，．
[3][M]2002马良斋：从递归算法看数学在计算机程序设计方面的应用
121112n n n F F F F F n +−==⎧⎨
=+≥⎩ ()
责任编辑：周玉云[]。
