并行递归算法

并行递归算法（精选七篇）

并行递归算法篇1

在很多有广泛应用背景的数学问题中,诸如样条逼近、最小二乘拟合、微分方程边值问题的差分方法以及有限元计算等,它们的求解最终都可归结为线性方程组的求解。因此,解线性方程组在科学与工程计算中有着十分重要的作用。线性方程组的有效求解方法是对其系数矩阵进行三角分解,常用的方法有LU分解和对称正定型线性方程组的Cholesky分解。为了有效地发挥计算机高速缓冲存储器的性能,一些专家学者提出了对系数矩阵进行分块,并设计实现了矩阵的LU递归分解算法,取得了较好的计算性能[1,2,3]。针对目前的微机普遍具有双核CPU的特点,设计实现了一种具有并行运算功能的矩阵LU递归分解算法。

1 矩阵的LU分解原理

考虑如下n元线性方程组

${\begin{matrix} a_{11} x_{1} + a_{12} x_{2} + \dots + a_{1 n} x_{n} = b_{1} \\ a_{21} x_{1} + a_{22} x_{2} + \dots + a_{2 n} x_{n} = b_{2} \\ ⋮ \\ a_{n 1} x_{1} + a_{n 2} x_{2} + \dots + a_{n n} x_{n} = b_{n} \end{matrix} (1)$

写成矩阵形式,有

$A x = b (2)$

式(2)中A=(aij)n×n, x=(x1,x2,…,xn)T, b=(b1,b2,…,bn)T。

当det(A)≠0(即A为非奇异矩阵)时,应用高斯主元素消元法对系数矩阵A施行一系列的初等行变换后,得到如下形式的上三角矩阵,记作U。

根据线性代数理论可知[4],对一个矩阵施行一次初等行变换运算,其实质就是该矩阵左乘一个初等矩阵的运算。所谓初等矩阵是指单位矩阵经过一次矩阵初等变换所得到的矩阵。设系数矩阵A(0)=A,当a $_{11}^{(0)}$ ≠0成立时,可构造如下的L1初等矩阵

$L_{1} = [\begin{matrix} 1 \\ - \frac{a_{21}^{(0)}}{a_{11}^{(0)}} & 1 \\ ⋱ \\ 1 \end{matrix}],$

则

$\begin{array}{l} L_{1} A = [\begin{matrix} 1 \\ - \frac{a_{21}^{(0)}}{a_{11}^{(0)}} & 1 \\ ⋱ \\ 1 \end{matrix}] \times \\ [\begin{matrix} a_{11}^{(0)} & a_{12}^{(0)} & \dots & a_{1 n}^{(0)} \\ a_{21}^{(0)} & a_{22}^{(0)} & \dots & a_{2 n}^{(0)} \\ ⋮ & ⋮ & ⋱ & ⋮ \\ a_{n 1}^{(0)} & a_{n 2}^{(0)} & \dots & a_{n n}^{(0)} \end{matrix}] = [\begin{matrix} a_{11}^{(0)} & a_{12}^{(0)} & \dots & a_{1 n}^{(0)} \\ 0 & a_{22}^{(1)} & \dots & a_{2 n}^{(1)} \\ a_{31}^{(0)} & a_{32}^{(0)} & \dots & a_{3 n}^{(0)} \\ ⋮ & ⋮ & ⋱ & ⋮ \\ a_{n 1}^{(0)} & a_{n 2}^{(0)} & \dots & a_{n n}^{(0)} \end{matrix}] (3) \end{array}$

式(3)中,

$a_{22}^{(1)} = - \frac{a_{21}^{(0)}}{a_{11}^{(0)}} a_{12}^{(0)} + a_{22}^{(0)}$ , $a_{2 n}^{(1)} = - \frac{a_{21}^{(0)}}{a_{11}^{(0)}} a_{1 n}^{(0)} + a_{2 n}^{(0)}$ 。

易知

$\begin{array}{l} L_{n - 1} \dots L_{2} L_{1} A = [\begin{matrix} 1 \\ 1 \\ ⋱ \\ - \frac{a_{n 1}^{(0)}}{a_{11}^{(0)}} & 1 \end{matrix}] \dots \\ [\begin{matrix} 1 \\ 1 \\ - \frac{a_{31}^{(0)}}{a_{11}^{(0)}} & ⋱ \\ 1 \end{matrix}] [\begin{matrix} 1 \\ - \frac{a_{21}^{(0)}}{a_{11}^{(0)}} & 1 \\ ⋱ \\ 1 \end{matrix}] \times \\ [\begin{matrix} a_{11}^{(0)} & a_{12}^{(0)} & \dots & a_{1 n}^{(0)} \\ a_{21}^{(0)} & a_{22}^{(0)} & \dots & a_{2 n}^{(0)} \\ ⋮ & ⋮ & ⋱ & ⋮ \\ a_{n 1}^{(0)} & a_{n 2}^{(0)} & \dots & a_{n n}^{(0)} \end{matrix}] = [\begin{matrix} a_{11}^{(0)} & a_{12}^{(0)} & \dots & a_{1 n}^{(0)} \\ 0 & a_{22}^{(1)} & \dots & a_{2 n}^{(1)} \\ ⋮ & ⋮ & ⋱ & ⋮ \\ 0 & a_{n 2}^{(1)} & \dots & a_{n n}^{(1)} \end{matrix}] (4) \end{array}$

当a $_{11}^{(0)}$ a $_{22}^{(1)}$ …a $_{(n - 1) (n - 1)}^{(n - 2)}$ ≠0时,有

$\begin{array}{l} L_{\frac{n (n - 1)}{2}} \dots L_{2} L_{1} A = [\begin{matrix} 1 \\ 1 \\ ⋱ \\ - \frac{a_{n, n - 1}^{(n - 2)}}{a_{n - 1, n - 1}^{(n - 2)}} & 1 \end{matrix}] \dots \\ [\begin{matrix} 1 \\ 1 \\ - \frac{a_{31}^{(0)}}{a_{11}^{(0)}} & ⋱ \\ 1 \end{matrix}] [\begin{matrix} 1 \\ - \frac{a_{21}^{(0)}}{a_{11}^{(0)}} & 1 \\ ⋱ \\ 1 \end{matrix}] \times \\ [\begin{matrix} a_{11}^{(0)} & a_{12}^{(0)} & \dots & a_{1 n}^{(0)} \\ a_{21}^{(0)} & a_{22}^{(0)} & \dots & a_{2 n}^{(0)} \\ ⋮ & ⋮ & ⋱ & ⋮ \\ a_{n 1}^{(0)} & a_{n 1}^{(0)} & \dots & a_{n n}^{(0)} \end{matrix}] = [\begin{matrix} a_{11}^{(0)} & a_{12}^{(0)} & \dots & a_{1 n}^{(0)} \\ a_{22}^{(1)} & \dots & a_{2 n}^{(1)} \\ ⋱ & ⋮ \\ a_{n n}^{(n - 1)} \end{matrix}] (5) \end{array}$

记 $L = (L_{\frac{n (n - 1)}{2}} \dots L_{2} L_{1})^{- 1}$ ,由于 $L_{i} (i = 1, 2, \dots, \frac{n (n - 1)}{2})$ 均为单位下三角矩阵,故L也为单位下三角矩阵,即

则(5)式可改写成

$\begin{array}{l} L^{- 1} A = U \Rightarrow A = L U = [\begin{matrix} 1 \\ l_{21} & 1 \\ ⋮ & ⋮ & ⋱ \\ l_{n 1} & \dots & 1 \end{matrix}] \times \\ [\begin{matrix} u_{11} & u_{12} & \dots & u_{1 n} \\ u_{22} & \dots & u_{2 n} \\ ⋱ & ⋮ \\ u_{n n} \end{matrix}] (6) \end{array}$

即矩阵A被分解为下三角矩阵L与上三角矩阵U之积。把式(6)代入式(2)有

$\begin{array}{l} A x = b \Rightarrow L U x = b \Rightarrow [\begin{matrix} 1 \\ l_{21} & 1 \\ ⋮ & ⋮ & ⋱ \\ l_{n 1} & l_{n 2} & \dots & 1 \end{matrix}] \times \\ [\begin{matrix} u_{11} & u_{12} & \dots & u_{1 n} \\ u_{22} & \dots & u_{2 n} \\ ⋱ & ⋮ \\ u_{n n} \end{matrix}] [\begin{matrix} x_{1} \\ x_{2} \\ ⋮ \\ x_{n} \end{matrix}] = [\begin{matrix} b_{1} \\ b_{2} \\ ⋮ \\ b_{n} \end{matrix}] (7) \end{array}$

令Ux=y,则Ly=b。由于这两组方程组均具有三角的形式,故通过回代的方式便很容易求y和x,这就是矩阵的LU分解原理。

给定n阶系数矩阵A,可运用Doolittle分解算法[5]来确定其下三角矩阵L和上三角矩阵U中的元素,具体计算公式为

${\begin{cases} u_{1 j} = a_{1 j} ‚ (j = 1, 2, \dots, n) \\ l_{i 1} = \frac{a_{i 1}}{u_{11}} ‚ (i = 2, 3, \dots, n) \\ u_{k j} = a_{k j} - \sum_{m = 1}^{k - 1} l_{k m} u_{m j} ‚ \\ (j = k, k + 1, \dots, n; k = 2, 3, \dots, n) \\ l_{i k} = \frac{a_{i k} - \sum_{m = 1}^{k - 1} l_{i m} u_{m k}}{u_{k k}} ‚ \\ (i = k + 1, k + 2, \dots, n; k = 2, 3, \dots, n) \end{cases} (8)$

2 矩阵的LU并行递归算法设计

在实际应用中,对于大型的线性方程组而言,其系数矩阵A的阶数n往往很大,若在计算机中直接按Doolittle分解算法的求解公式来进行计算,则无法发挥当前高性能计算机多级存储结构的高速缓冲存储器(cache,该存储器的容量一般较少)的作用,为此,文献[1,2,3]设计实现了矩阵的LU分块分解算法,其原理如下。

把系数矩阵A及其LU分解后的上、下三角矩阵都分成为一个2×2分块矩阵,有

$[\begin{matrix} A_{11} & A_{12} \\ A_{21} & A_{22} \end{matrix}] = [\begin{matrix} L_{11} \\ L_{21} & L_{22} \end{matrix}] [\begin{matrix} U_{11} & U_{12} \\ U_{22} \end{matrix}] (9)$

式(9)中A11, L11和U11∈Rr×r;A12和U12∈Rr×(n-r);A21和L21∈R(n-r)×r;A22和L22,U22∈R(n-r)×(n-r),(r<n)。这里,L11和L22、U11和U22仍为上、下三角矩阵,而r的大小则取决于计算机高速缓冲存储器的大小。

从式(9)有

$\begin{array}{l} A_{11} = L_{11} U_{11} (10) \\ A_{12} = L_{11} U_{12} (11) \\ A_{21} = L_{21} U_{11} (12) \\ A_{22} = L_{21} U_{12} + L_{22} U_{22} (13) \end{array}$

运用Doolittle算法高速缓冲存储器中在对A11进行LU分解求得L11和U11后,便可计算出

U12=L $_{11}^{- 1}$ A12,L21=A21U $_{11}^{- 1}$ 。

从(13)式可知

L22U22=A22-L21U12。

记A22-L21U12为A(1),显然,对A(1)施行LU分解便可求得L22和U22。改写(9)式,有

$\begin{array}{l} A = [\begin{matrix} A_{11} & A_{12} \\ A_{21} & A_{22} \end{matrix}] = [\begin{matrix} L_{11} = (A_{11})_{L} \\ L_{21} = A_{21} U_{11}^{- 1} & L_{22} = (A^{1})_{L} \end{matrix}] \times \\ [\begin{matrix} U_{11} = (A_{11})_{U} & U_{12} = L_{11}^{- 1} A_{12} \\ U_{22} = (A^{1})_{U} \end{matrix}] 。 \end{array}$

同理,当A(1)的阶数仍然很大(n-r>r)时,则可以继续采用上述分块矩阵的方法进行LU分解,以确保各分块矩阵的相关运算可以在高速缓冲存储器中进行。把A(1)分成为一个2×2分块矩阵后,进行LU分解,有

$\begin{array}{l} A = \\ [\begin{matrix} L_{11} \\ L_{21} & \begin{matrix} L_{11}^{(1)} = (A_{11}^{(1)})_{L} \\ L_{21}^{(1)} = A_{21}^{(1)} (U_{11}^{(1)})^{- 1} & L_{22}^{(1)} = (A_{}^{(2)})_{L} \end{matrix} \end{matrix}] \times \\ [\begin{matrix} U_{11} & U_{12} \\ \begin{matrix} U_{11}^{(1)} = (A_{11}^{(1)})_{U} & U_{12}^{(1)} = (L_{11}^{(1)})^{- 1} (A_{12}^{(1)}) \\ U_{22} = (A_{}^{(2)})_{L} \end{matrix} \end{matrix}] 。 \end{array}$

上述过程进行m次后,直至A(m)的阶数小于r结束,此时有

$\begin{array}{l} A = [\begin{matrix} L_{11} \\ L_{21} & \begin{matrix} L_{11}^{(1)} \\ L_{21}^{(2)} & \begin{matrix} ⋱ \\ \begin{matrix} \dots & \begin{matrix} L_{11}^{(m)} \\ L_{21}^{(m)} & L_{22}^{(m)} \end{matrix} \end{matrix} \end{matrix} \end{matrix} \end{matrix}] \times \\ [\begin{matrix} U_{11} & U_{12} \\ \begin{matrix} U_{11}^{(1)} & U_{12}^{(1)} \\ \begin{matrix} ⋱ ⋮ \\ \begin{matrix} \begin{matrix} U_{11}^{(m)} & U_{12}^{(m)} \\ U_{22}^{(m)} \end{matrix} \end{matrix} \end{matrix} \end{matrix} \end{matrix}] (14) \end{array}$

式(14)中的迭代运算在计算机数值计算中可用递归算法来完成.由于式(11)和式(12)中的U12、L21之间的计算并没有依赖关系,所以它们可以分别独立地并行计算。考虑到当前的微机普遍具备双核CPU,本文提出了如下的矩阵LU并行递归分解算法[6,7]。

算法名称: 矩阵的LU并行递归分解算法。

输入:n阶系数矩阵A,分块子矩阵A11的阶数r。

输出:系数矩阵A的LU分解元素。

算法描述:

3 算法的性能测试

为了验证新设计算法的可行性和有效性,进行了相关的实验测试。测试的硬件环境为Intel Pentium(R) Dual-Corel E5700 双核CPU(单个CPU的频率为3 GHz),KingSton DDR3 1 333 MHz 2 GB;软件环境为Microsoft Windows XP Professional Service Pack 3,Microsoft Visual C++ 2008 +OpenMP程序包.在上述环境中,用VC分别编写及调试了传统的Doolittle矩阵LU分解算法、递归分块算法及新设计的并行递归分块算法。在实际调试过程中,递归函数中的分块矩阵的阶数r选取300左右时,递归分块算法的性能将达到最佳。各个算法的实际运行结果如表1所示。

从表1可以发现,随着系数矩阵A的阶数的增加,新设计的算法比前两种算法的运算速度分别提高了近70%和30%。

4 结语

在PC双核微机上设计实现了一种矩阵并行递归LU求解算法,该算法不仅有效地利用了CPU中的高速缓冲存储器,而且有效地发挥了双核CPU的功能。算例测试证实算法的可行性及有效性。

参考文献

[1]陈建平.LU分解递归算法的实现.数值计算与计算机应用,2004;25(4):315—320

[2]陈建平.LU分解递归算法的研究.计算机科学,2004;31(6):141—142

[3]陈建平.矩阵三角分解递归算法的研究与实现.上海:上海大学硕士论文,2005:6—23

[4]卢琳璋.线性代数.北京:科学出版社,2001:49—66

[5]程云鹏.矩阵论.西安:西北工业大学出版社,2001:178—234

[6]周伟明.多核计算与程序设计.武汉:华中科技大学出版社,2009:75—124

并行递归算法篇2

随着计算机信息技术的不断发展, 软件行业与程序设计行业得到了前所未有的发展。越来越多的智能产品离不开先进计算机技术的支持。递归是程序设计中一种重要的解决办法, 同时递归法也是一种计算机技术的发展思路, 通过递归的方法实现庞大的工作量的简化, 以提高工作效率, 降低劳动强度, 适合社会的高速发展。掌握好递归程序设计算法需要牢固的基础知识, 同时经过长期的工作经验总结, 才能运用自如。本文通过对递归法与转化而成的非递归算法进行研究, 以供参考。

2 递归算法定义

随着程序设计者的意图不同, 相互间可能会存在着一定的不协调性。利用递归的算法可以通过对自身程序进行调用, 化解成多个小的问题, 一一进行解决后对原问题进行解决的过程。对调用过程中的信息进行保存和恢复。递归算法的过程中相对简单, 主要分为递推与回归两个部分, 递推主要是为了得到问题的角, 把问题推向更简单的方向, 回归主要是指在简单的问题得到解答后, 回归到原来的复杂问题中。在递归算法的实际应用过程中, 递归算法所涉及到的参数与局部变量是有层次区分的。

3 递归算法的条件与优缺点

当在程序中需要解决的问题可以向另一个问题进行转化时, 二者在解决办法相同, 但处理的对象有所不同, 这是递归算法应用时的一个基本条件, 另外就是具备终止的递归条件, 在转化的过程中, 在特定条件已经得到解, 无需再继续进行分解。递归设计的本质是当一个复杂的问题可以分解成几个子问题来进行处理时, 这些子问题与原来的问题分析处理方法相同。当子问题解决时, 原来的问题自然也就解决了, 递归的定义归纳项就是对这种转化关系进行描述。

例求n! (n为正整数) 。

在案例中直接调用factorial (n-1) 本身函数进行求解的办法进行, 称为直接递归函数。

每一种算法都存在客观的优缺性, 递归算法的优点是结构非常清晰, 可读性强, 而且容易使用数学归纳的方法来对算法的正确性进行证明, 给调试程序带来了极大的便利, 同时递归算法也有其缺点, 它的运行效率偏低, 在耗费的计算时间、存储空间都相对于非递归算法要多的多。

4 如何进行非递归算法转化

基于递归算法有优点和缺点, 在运用时要对方法进行有效的选择, 才能有效求解。经过长期的发展, 人们更愿意采用递归的算法来对问题进行分析, 而对于问题的求解则是多通过非递归算法来进行, 这其中就需要将递归算法转化为非递归的算法。

转化过程就是分析的过程, 把递归算法转换成非递归算法是对递归函数系统的执行过程的一种模拟, 这种构造的非递归算法语句较多, 但由于固定方法可以遵循, 在实际的软件设计使用的频率较多。首先对栈S进行初始化, 给每一个递归的函数入口分别进行不同的标号, 每个返回处设立一个标号, 把每个递归函数的递归调用进行如下操作转化。对现场进行保留, 开辟存储空间, 准备数据, 转入相应的进归函数执行。在特殊情况下也可以进行简化, 简化规则主要有三种方式。如果在递归算法只有一处递归调用或多个调用返回时, 所执行的语句都相同, 则在转换时, 返回地址可以不必入栈, 只为参数设立栈进行保存。

递归算法转化为非递归算法主要有三种形式。首先是通过分析, 不用分解, 直接用循环的算法实现求解;二是自己运行时栈, 对分析过程中的信息进行存储, 转化为非递归算法替代递归算法;三是利用栈保存参数, 由于栈本身具有典型的先进后出的性质, 与递归算法的执行过程相匹配, 因而可利用非递归算法来对递归算法进行替代。本文主要对直接转化与借助借助栈实现转化。

4.1 直接转化法

在递归算法的函数中, 递归调用语名只有一个, 这种递归称为尾递归, 这个调用语句位于函数的最末端, 当调用返回时, 返回到上一层算法的结束处。用迭代形式来对其进行代替, 不再使用系统运行时的栈来对信息进行保护。阶乘求解就可以写成如下所示的非递归算法。

4.2 借助栈实现转化

递归在调用时与在调用过程中重要的一环是递归函数运行的层次。层次具有典型的重要意义, 调用该函数的主函数如果是第0层开始的话, 从主函数调用递归函数在进入到第1层, 以此类推, 在第i层递归调用函数为进入到下一层 (i+1层) 。相反, 则会退到i-1层。为了确保运行过程能够正常操作, 系统需要设置“递归工作栈”, 来作为递归函数运行期间使用的数据存储区。每一个层的递归所需要的信息都会形成一个工作记录, 相当于痕迹, 记录着相关的参数据, 工作记录中包括递归所需要的信息, 有实在参数、局部变量与上层的返回地址等。当进入到层递归时, 将形成新的工作记录, 而退出一层时, 将会在栈顶弹出一个工作记录。通过栈来实现非递归转化具有典型的意义, 目前应用较为广泛

5 结语

递归算法有其自身的优势与缺点, 与非递归算法在运行的效率上与适应性方面有所不同。本文通过对递归算法与非递归算法的转化思路分析, 不断提高其执行效率, 解决目前面临的实际问题。针对不同的运行环境与要求, 需要选择不同的算法, 不可盲目地用栈来对递归进行消解。采用借助栈的方式进行转化并不能切实提高计算机求解问题的运行时间, 但可以节省系统的堆栈, 适合于不支持递归机制的语言进行程序设计。随着计算机编程技术的不断进步, 将会出现新的算法, 提高运行效率, 适用于更多的计算环境与要求。

摘要：递归算法是程序设计中一种重要的工具, 基于长时间的实践, 发现其存在着一定的优势与缺点。递归法与非递归法存在着一定的区别, 同时递归算法不适合某些程序进行计算解决问题, 本文重点对其非递归算法转化过程进行分析, 以供参考。

关键词：递归,非递归,算法,条件,实质,转化

参考文献

[1]马海瑛.数据结构中递归算法的描述与实现[J].大众科技, 2007, 03:177-178+153.

[2]马军红.递归与非递归算法比较及效率分析[J].科技信息, 2008, 31:554+566.

[3]高鹭, 周李涌.递归算法及其转化为非递归算法的分析[J].科技资讯, 2008, 30:210.

[4]聂雅卓, 周步祥, 林楠, 高志勇, 刘金华.多电压等级电网可靠性递归原理及其递推算法[J].电力系统及其自动化学报, 2012, 05:117-122.

[5]李伟.浅析C语言递归算法[J].电脑知识与技术, 2012, 30:7229-7235.

[6]汤亚玲.递归算法设计及其非递归化研究[J].计算机技术与发展, 2009, 11:85-88+93.

浅析C语言递归算法篇3

关键词：递归,算法,消除,程序,应用

1 递归概念

1.1 概述

本文阐述了递归算法的基本定义、成立的必要条件和递归执行的特点以及在实例中的具体应用, 让学生能理解“递归是一种思想”这个概念。

在生活实际中, 有些问题是不能用数学公式解决的, 需要通过其他方式、其他算法才能完成, 其他重要算法有分治法、回朔法和动态规划等。分治法的三个步骤为: (1) 分解:将当前区间一分为二, 求分裂点; (2) 求解:递归地对两个子区间进行归并排序; (3) 组合:将已排序的两个子区间归并为一个有序的区间。其递归的终结条件:子区间长度为1 (一个记录自然有序) 。回朔法的三个步骤: (1) 搜索策略:符合递归算法, 问题解决可以化为子问题, 其子问题算法和原问题相同, 只是数据增大或减少; (2) 控制策略:避免不必要的穷举搜索, 遇到搜索失败, 从失败点返回到上一点重新搜索; (3) 数据结构:用数组保存搜索过程中的状态、路径。可见, 其他算法依然以递归算法为基础, 利用递归帮助解决问题。

1.2 概念和成立条件

递归是设计和描述算法的一种有力的工具, 它在复杂算法的描述中被经常采用

1.2.1 概念

一个函数、过程、概念或数学结构, 如果在其定义或说明内部直接地或间接地出现有其本身的引用, 或者是为了描述问题的某一状态, 必须用到它的上一状态, 而描述上一状态, 又必须用到它的上一状态………这种用自己定义自己的方法, 称之为递归或者是递归定义。

1.2.2 成立条件

应满足三点: (1) 符合递归的描述:需要解决的问题可以化为子问题求解, 而子问题求解的方法与原问题相同, 只是数量增大或减少; (2) 递归调用的次数是有限的; (3) 必须有递归结束的条件。

1.3 递归分类

1.3.1 直接递归

程序设计中, 过程或函数直接或者间接调用自己, 就被称为递归调用。子程序直接调用自己, 这称为直接递归;嵌套关系的子程序A和B, 内层的B调用外层的A, 这是间接低归;平级关系的子程序A和B, 其中A调用了B, B调用了A, 这也是间接递归, 不过, 这种间接递归用到了“超前引用”的规则。

《例》输入一串以“#”结束的字符, 按逆序输出。

程序中, c是过程rever的局部变量。每一次递归调用, 都要为局部变量重新分配单元, 因此每个层的变量c实际上是不同的量, 他们分别用于保存本层调用时的输入值。

输入god#的调用过程如下图1所表示。

1.3.2 间接递归

除了以上直接递归的例子外, 在某些问题中, 还会出现间接递归的情况, 如图2所表示。

2 递归本质

2.1 函数递归调用机制

递归函数调用同样遵守函数调用机制, 当函数调用自己时也要将函数状态、返回地址、函数参数、局部变量压入栈中进行保存。

实际上函数被调用时执行的代码是函数的一个副本, 与调用函数的代码无关。当一个函数被调用两次, 则函数就会有两个副本在内存中运行, 每个副本都有自己的栈空间且与调用函数的栈空间不同, 因此不会相互影响。这种调用机制决定了函数是可以递归调用的。

2.2 递归调用优缺点

递归使一些复杂的问题处理起来简单明了, 尤其在学习算法设计、数据结构时更能体会到这一点。但是, 递归在每一次执行时都要为局部变量、返回地址分配栈空间 (对方法的每次递归调用都会生成新的局部变量和局部参数。假如递归层次太多的话, 就会消耗太多的stack) , 这就降低了运行效率, 也限制了递归的深度。因此, 在必要的时候可以只使用递归的思想来求解, 而程序则转用非递归的方式书写。

3 递归的应用

3.1 递归定义的数据结构

3.1.1 二叉树 (定义)

二叉树的递归定义二叉树或者是一棵空树, 或者是一棵由一个根结点和两棵互不相交的左子树和右子树所组成的非空树, 左子树和右子树又同样都是二叉树。

下面介绍二叉树的二叉链式存储结构。我们先给出二叉链表链结点类型描述:

tnode为链表结点类型名, tlink为指向链结点的指针类型, elemtp为结点数据的类型.

那么如何根据输入的数据建立二叉链表呢?设二叉树结点数据类型为字符型, 各结点数据按照二叉树的数组表示方式存储在字符串str中, 字符串变量为s;string、整型变量为n;integer及指针为root;tlink, 它们已经在外部说明, 则二叉链表的建立过程可表示为procedure build (str;string) ;其功能为根据字符串str的内容建立二叉树的二叉链表, 并让root指向这个二叉链表。其处理过程为:以1为参数调用递归子函数function build0 (i;integer) :tilink完成二叉链表的建立, 并让root指向该链表。递归子函数function build0 (i;integer) :tilink的功能为:以字符串str的第i个元素为二叉树的根结点递归的建立二叉链表, 并返回指向该链表的指针。其处理过程为:

若i小于字符串的长度, 且字符串的第i个元素为非空格符, 则创建一个链结点, 在其数据域中存放字符串的第i个元素;

以2*i为参数, 调用build0建立这个结点的左子树;

以2*i+1为参数, 调用build0建立这个结点的右子树;

以下是程序清单:

3.2 递归定义函数

3.2.1 阶乘

《例》用递归计算n!

n!可以由下列公式表示:

这是递归定义简单而典型的例子。把求n!转化为求 (n-1) !的问题, 因为 (n-1) !乘上n就是n!。而求 (n-1) !又可以转化为 (n-2) !的问题……最后归结为求0!的问题, 而0!已定义为1。由0!=1又一步步返上去求出1!, 2!, ……直到求出n!。

程序清单:

3.3 递归定义过程

3.3.1 树的遍历

根据二叉树的递归定义, 一棵非空二叉树由根结点、左子树和右子树组成, 因此遍历一棵非空二叉树的问题可分解为三个问题, 即访问根结点、遍历左子树和遍历右子树。显然, 遍历左、右子树的问题仍然遍历二叉树的问题, 所以二叉树的这三种遍历方式可以用递归算法实现。

我们以遍历方案DLR (因为访问根结点的操作在遍历左、右子树之前, 故称之为前序遍历或先根遍历) 为例, 若二叉树不为空, 则

访问根结点;

以前序遍历方式遍历根结点的左子树;

以前序遍历方式遍历根结点的右子树;

设p为指向二叉树根结点的指针, 则前序遍历过程可表示为procedure preorder0 (p:tlink) ,

其功能为对p所指的二叉树进行前序遍历, 输出前序遍历的结点序列, 其处理过程为:

若p非空, 则

(1) 显示p所指的结点数据;

(2) 前序遍历p所指的左子树;

(3) 前序遍历p所指的右子树;

以下为程序清单:

4 递归消除

为了提高算法的程序运行速度及减少占用内存空间, 和透切理解递归递归机制 (这种理解是熟练掌握递归程序技能的必要前提) , 我们接下来探讨递归消除。

递归消除, 就是将一个递归算法转化为等价的非递归算法。递归消除一般有两种方法:

一、基于循环的递归消除。不是用工作栈作为工作机制, 而是利用循环算法, 即采用递推算法, 这样可避免重复计算, 提高了效率, 如下面所要讲的斐波那契数列。

二、基于栈的递归消除。大部分递归问题无法用递推算法来消除, 在这种情况下, 引用一个工作栈作为控制机构以消除递归算法, 其原理是:利用数组模拟工作栈, 保存“返回位置”, 以实现过程调用和返回控制。

4.1 利用栈消除递归

我们以Hanoi (河内/汉诺) 塔问题为例, 看如何利用数组建立的栈来消除递归的。

例:Hanoi (河内/汉诺) 塔问题

有n个圆盘, 依半径大小 (半径都不同) , 自下而上套在A柱上, 每次只允许移动最上面的一个盘子到另外的柱子上去 (除A柱子外, 还有B柱子和C柱子, 开始时这两个柱子上没盘子) , 但绝不允许发生柱子上出现大盘子在上, 小盘子在下的情况, 现在要求设计将A柱子上n个盘子搬到C柱子上去的方法。

问题解析:本题是典型的递归程序设计题。

1) 当n=1时, 只有一个盘子, 只需要移动一次:AC;

2) 当n=2时, 则需要移动三次:

3) 当n=3时, 需要将前2个盘子移到B柱子, 再将第三个盘子移到C柱子, 然后将2个在B柱子上的盘子借助A柱子移动到C柱子, 因此可以得到移动盘子的一般规律:

a.先将n-1个盘子从A柱子移动到B柱子, C柱子为中间柱子;

b.将第n个盘子从A柱子移动到C柱子;

c.再将n-1个盘子从B柱子移动到C柱子, A柱子为中间柱子。

其程序如下:

主程序:

为了保证递归调用正确执行, 系统要建立一个递归调用工作栈, 为各层次的调用分配数据存储区。每一层递归调用所需要的信息构成一个工作记录, 其中包括所有实参指针, 所有局部变量以及返回上一层的地址。每进入一层递归调用, 就产生一个新的工作记录压入栈顶。每退出一层递归调用, 就从栈顶弹出一个工作记录。

4.2 利用循环消除递归

例:用递归的方法求斐波那契数列中的第n个数

程序清单如下:

递归算法求斐波那契数列中的第n个数, 是从大到小逐步处理的。先把fib (n) 拆分为fib (n-1) 和fib (n-2) , 而每一部分又再拆分为两部分……总的递归次数是2n-1, 计算量是很大的, 且存在很多重复计算。如果我们从小到大来考虑这个问题, 就会得到这样一个递推关系:

这样, 就可以将递归程序转化为非递归的程序了。

斐波那契数列用非递归算法求解的程序如下:

5 总结

总的说来, 递归是一种非常重要的, 应用很广泛的程序设计方法。递归的能力在于用有限的语句来定义对象的无限集合。用递归思想写出的程序往往十分

简洁易懂, 结构清晰, 形式简单, 符合人们的日常思维习惯, 容易被理解和阅读。其他算法, 如分治法, 有许多是源于递归思想, 或是由递归分解+合并处理, 还有如回朔法和动态规划问题, 动态规划的子问题重叠性质与递归有某种相似之处, 递归+动态修改查表是一种不错的建立动态规划模型的方法。可见, 掌握递归算法、理解递归思想对于学习其他程序设计方法也是很有帮助的。

递归使一些复杂的问题处理起来简单明了, 尤其在学习算法设计、数据结构时更能体会到这一点。但是, 递归在每一次执行时都要为局部变量、返回地址分配栈空间, 假如递归层次太多的话, 就会消耗太多的stack, 对内存要求很高, 这就降低了程序运行效率, 也限制了递归的层次和深度。因此, 在必要的时候可以只使用递归的思想来求解, 而程序则转用非递归的方式书写。

参考文献

[1]吴再陵, 高建军.全国青少年信息学培训教材[M].南京:南京大学出版社, 2002.

[2]朱振元, 朱承.数据结构教程--面向对象实现方法[M].西安:西安电子科技大学出版社, 2000.

[3]邓毅.Delphi4.0入门与提高[M].北京:清华大学出版社, 1999.

[4]严蔚敏.数据结构[M].北京:清华大学出版社, 1992.

[5]李大友.数据结构与算法[M].北京:机械工业出版社, 1996.

全排列的递归算法实现篇4

从n个不同元素中任取m(m≤n)个元素,按照一定的顺序排列起来,叫做从n个不同元素中取出m个元素的一个排列。当m=n时所有的排列情况叫全排列[1]。

某全排序问题:将一个字符组全排序。输入文件(Sortwide.in)包含一个长度小于8的字符串,该字符串由数字1~9组成,字符不会重复出现;要求按数字从小到大的顺序输出该字符组的全排序,并将结果保存在文件中(Sortwide.out)。

2 递归算法

2.1 基本概念

直接或间接地调用自身的算法称为递归算法。用函数自身给出定义的函数称为递归函数。使用递归技术可以使函数的定义和算法的描述简洁且易于理解。有些数据结构如二叉树,由于其本身固有的递归特性,特别适合用递归的形式来描述。另外有些问题,虽然本身没有明显的递归结构,但用递归技术来求解使设计出的算法简洁易懂且易于分析[1]。

2.2 过程实现

递归算法包括“递推”和“回归”2部分[1]。

2.2.1 递推

递推就是为得到问题的解,将它推到比原问题简单的问题的求解。递推应有终止之时,即有所谓的“终止条件”,在此条件下,问题的解是明确的;“简单问题”表示离递推终止条件更为接近的问题。

2.2.2 回归

回归指当“简单问题”得到解后,回归到原问题的解上来。

3 C语言递归编程求解全排列

C语言是国际上广泛流行的功能强大的高级程序设计语言,语言简洁、紧凑,使用方便、灵活[2]。采用C语言可以很方便地解决全排列问题。

3.1 数据结构

数据结构[3]是计算机存储、组织数据的方式。精心选择的数据结构可以带来更高的运行或者存储效率的算法。一个数据结构是由数据元素依据某种逻辑联系组织起来的。在不同的程序设计语言中,选择不同的数据结构,可以得到高效的题解。

在C语言中主要构造一维数组char list[],用以存放排列序列,并将其设置为全局变量。为统计总共排列个数,设置一个全局变量,初始值为0,即int n=0,(如果字符达到8个,则需设置为long n=0);设置一个全局变量len,用以记录字符长度,初始值为0,即int len=0。

3.2 全排列的递归求解思想和函数void perm(int k,int m)

3.2.1 递归求解思想

设R={r0,r1,…,rn-1}是要进行排列的n个元素,观察当n=1,n=2,n=3时的全排列。

将n=3时的全排列分成3组,可得第1组是由r1与r2的全排列加上前缀r0得到的,第2组是由r0与r2的全排列加上前缀r1得到的,依此类推可知,3个元素的全排列问题可转化成求2个元素的全排列问题;从而n个元素的全排列问题可转化成求n-1个元素的全排列问题,由此找到递归关系。引入记号perm(R)表示集合R的全排列,Ri=R-{ri},{ri}perm(Ri)表示集合除ri元素外的所有元素的全排列前加上前缀ri后得到的排列。则R的全排列递归定义为:

3.2.2 构造递归函数

函数Perm(Object[]list,int k,int m)[4]是求将list的第0~k-1个元素作为前缀、第k~m-1个元素进行全排列得到的全排列,如果k为0,且m为n,就可以求得一个数组中所有元素的全排列。全排列的递归构造过程就是对全排列树的深度优先搜索过程,其递归函数中主要过程为当k

事实上,当list作为全局变量出现时,swap(list,k,i)可以写成swap(k,i),而不用作为参数传递;其交换函数也就为常规地将相应的2个值交换;

该递归算法能够求解出全排列,但不能够满足按数字从小到大的顺序输出要求;和文献4相比,改进递归算法思想:修改递归中的交换操作,具体交换见下文描述的函数swap1(k,i)和swap2(k,i)。例如序列1、2、3、4、5;当k=1,i=3时;原递归思想操作为,交换1、3位置的值得到1、4、3、2、5,然后递归调用,再交换1、3位置回到原序列1、2、3、4、5,其交换如图1所示。改进的算法思想为交换1、3位置时不再是单纯地交换1、3位置,而是将1、2位置的值移到2、3位置,3位置的值交换到1位置,得到1、4、2、3、5,然后递归调用,再交换回到原序列1、2、3、4、5。2次交换分别如图2、图3所示。

3.2.3 两个重要的交换函数

void swap2(int a,int b)类似于swap1,不再完整给出。

3.2.4 完整递归函数

3.3 读取待全排序的字符组函数int in_file_qpl()

本函数的sort()函数用来完成将初始输入的字符序列list从小到大排序,可以采用直接选择法或者冒泡法编写。

3.4 完整程序

上文中已经完整给出的sort()、in_file_qpl()、swap1()、swap2()以及perm()函数,不再详细描述,函数体部分均使用{…}替代。

4 仿真结果

使用笔记本电脑IBMR50e,CPU主频1.6 GHz,512M内存,Windows XP操作系统,Turboc 2.0环境运行。Sortwide.in文件中内容为15342,运行本程序,可以迅速得到解文件Sortwide out,其中包含了120个从小到大排序的全排列结果,耗时0.4秒;当内容为1376452时,排列7个字符时,本程序虽然将结果既输出到屏幕同时又输出到文件,耗时也仅为2.8秒。

5 结语

对全排列组合的递归求解不仅能够体现了递归算法的优点,而且给出了利用递归算法解决类似问题的一个思路;掌握递归思想,巧妙地利用递归算法可以解决许多数学难题。

摘要：递归算法的设计与实现是非常重要的内容,全排列是组合数学中最常见的问题。提出了基于递归算法并通过C语言编程实现了计算机解题,实例数据表明程序非常高效。

关键词：递归,全排列,全排列递归算法

参考文献

[1]王晓东.算法设计与分析[M].北京:清华大学出版社,2003,1:19.

[2]谭浩强.C程序设计[M].3版.北京:清华大学出版社,2005,1:3,140-143,171-177,342.

[3]严蔚敏,吴伟民.数据结构[M].2版.北京:清华大学出版社,1993,6:93-95,43-45,220-221.

递归算法的分析与应用篇5

关键词：递归算法,树,图,折半查找

1 递归算法的分析

要知道如何使用递归算法, 就必须要先掌握递归的概念、递归的思想及递归的特点, 本节介绍了递归的概念及递归算法所具有的特点, 从而更好的掌握递归的思想。

1.1 递归的概念

递归就是把复杂的问题化成同类型的小规模的子问题, 比如数的阶乘就是把N个数的连乘分解成X*F (X-1) 即两个数相乘的问题, 然后不断的改变X的值递归的调用这个小问题的函数F (X-1) 。当X等于0时返回1, 此次递归调用结束, 否则返回X*F (X-1) 即继续递归调用F函数。从数的阶乘中我们可以看到递归算法就是直接或者间接的调用自己的算法, 体现一个重复的过程, 而这个重复又体现递归思想的三个方面:

(1) 每次重复调用递归算法时, 问题的规模都比上次要小;

(2) 相邻两次的递归调用之间有紧密的连续, 前一次为后一次做准备。比如在数的阶乘算法中, 要计算出N的阶乘, 则需要计算出N* (N-1) !, 即要计算出N-1的阶乘, 也就是计算N的阶乘的函数会递归调用计算N-1阶乘的函数, 如此递归调用下去直到N减小到1时停车递归算法的调用。

(3) 这个重复不是无止境的, 必须有一个条件控制函数的递归调用, 如数的阶乘中函数F (X) 中的参数X就是一个条件, 当X减小到1时直接给出答案, 否则才递归的调用F函数。如果重复是无条件的, 则必定会带来死循环, 所以递归算法中要注意递归条件的控制。

1.2 递归算法的特点

递归算法是将规模大的复杂问题化成小规模的同种问题, 这种方法使问题的解决简单化, 对解决程序中具有相同子问题的复杂问题有很大的作用, 同时使问题的描述更简洁和更方便人理解。递归算法具有以下三个方面特点:

(1) 递归就是间接或直接的调用自身的过程。

(2) 递归算法必须有一个入口和一个出口, 入口通常就是函数的开始, 而出口即结束递归的条件, 如数的阶乘中当X等于0时即为递归的出口。

(3) 由于递归本身的特性, 每运行一次递归程序, 系统就要将这一层调用的函数返回地址和其中的局部变量保存在栈中, 当递归的次数过多时就会造成栈溢出, 所以要注意递归的算法设计。

2 递归算法的应用

2.1 递归算法在树中的应用

由于树的具有分支的特性, 即树的一个小分支又是一颗小的树, 所以在于树有关的问题中通常采用递归的算法。这里讲的树的应用是在一个机器的销售统计系统中将机器按照编码显示成树的形式, 机器的编码总共为12位, 按照机器的分类要求将编码分为5个层次, 总分 (1位) +大类 (2位) +中分 (2位) +小分 (2位) +细类 (5位) , 之所以这样分类是系统中所有的机器分为5类:A产品、B部品、C工程材料、D物流、E经费, 依次编号为1~5, 这样分类当我们需要查找B部品时只需在编码2开头的机器中查找即可, 其他分类均以此要求。

要将系统中所有的机器按照如下图1的形式显示出来, 我们将用到递归的思想, 下面介绍如何利用递归思想实现机器树的显示。

树中每一个节点都是一个Node, Node类中有其相关的属性如当前Node属于树中那一层、所表示的名称以及Node List列表中包含当前节点下的所有子节点, 当然子节点中又会包含子节点的子节点, 这样的嵌套包含最终形成树的形式。在这里我们主要介绍如何将数据库中读出的所有机器列表组合成一个机器树的形式, 这种递归是自身调用自身的程序。假设我们将101010100001这个编码的机器加入机器树中, 首先我们要在机器树种查询大类为1的机器编码是否存在, 如果存在则在这个节点下继续添加, 如果不存在则新建编码为1的节点, 然后在此节点下将其余编码分4层分别加入该节点的子节点, 其中每一层机器编码的添加都是如此, 这样我们想到利用递归的算法实现机器添加函数。

函数的主要功能是将一个机器按编号添加到机器树种, 由于机器编号分层, 即要按照层次加入其中。以下以编号101010100001为例解释该程序流程图。函数的参数有父节点, 当前层次, 要添加到树中的机器编号。进入程序后新建当前要加入的节点, 并根据参数为新节点层数和编号赋值, 该新节点即是要加入机器树中的节点。因为递归算法的出口点是机器的层数, 机器总共分为5层, 如果为前4层中的编号, 都要递归调用此添加函数, 但如果为第5层, 即将该机器编号中的所有编号按照层次都添加进去了, 即该机器添加完成, 所以该递归算法的出口点是当前层次为最后一层。所以先判断当前层是否为最后一层, 如果为最后一层则直接将该新建节点加入父节点的子节点列表中, 即退出这一层的递归程序。如果不为最后一层, 则先判断父节点是否有子节点, 判断父节点中是否有子节点是为了检查该层下面是否有已经存在的子层。如果当前父节点存在子节点, 则遍历所有的子节点, 在子节点列表中寻找与当前节点前两个编号相同的子节点 (因为能进入这一层的都是寻找第二、第三、第四层的编号, 而这三层的编号都为2位数字) , 如果寻找到则将当前节点赋值给父节点, 当前层数加1, 当前机器编号去除前两位, 此为递归条件的改变, 递归调用该程序。如果遍历所有的子节点列表都没有找到与当前节点相同的编号, 则将当前节点加入父节点后再修改递归的条件, 再次调用该程序。

2.2 递归算法在图中的应用

递归算法在图中的应用主要讲跳棋游戏中寻找棋子可跳动位置的算法。当玩家为电脑时, 电脑落子的程序会从当前棋子的可跳动位置数组中选择一个最佳的位置来跳动, 由于所选的位置只在可跳动位置数组中, 这也保证了电脑落子是按照游戏规则来的。这里棋子有两种跳动方式, 一种是跳向相邻位置, 另一种是棋子的连续隔子跳动。这样我们根据递归算法的思想设计函数, 其递归调用结构图如下图2:

棋盘中的棋子总共有122颗, 循环依次为每颗棋子根据跳棋游戏的规则寻找可跳动位置, 保存在可跳动位置数组中。首先用Chess保存当前棋子, 即我们现在的工作是寻找棋子Chess的可跳动位置。当我们寻找到棋子的一个可跳动位置Place, 将Place加入Chess的可跳动位置, 接着递归调用寻找棋子可跳动位置的函数, 只是此时将寻找可跳动位置函数的参数改为Place, 即接着寻找Place的可跳动位置Place1, 如果寻找到则将新位置Place1加入Chess的可跳动位置, 然后将Place1作为新的参数再次调用寻找可跳动位置函数, 直到参数中的棋子不再有可隔子跳动的位置即结束当前递归程序, 回到递归的上一层。这样就实现Chess的连续跳动, 即Chess可跳动到Place, 然后再跳动到Place1……, 当整个递归函数结束后, 修改当前的棋子Chess, 即寻找下一个棋子的可跳动位置。

2.3 递归算法在折半查找算法中的应用

当一列数或字母等是按照有序排列时, 为了寻找其中的某个数组或字母, 高效的查询方式是折半查找, 折半查找充分体现了递归算法中规模折半减小的特点, 每递归调用一次函数, 查找的范围就减小一半, 如下图3为折半查找程序流程图:

本论文对递归的算法进行分析, 主要介绍递归算法的概念和递归的特点, 只有掌握递归的思想和了解递归的特点, 才能将问题分析的更透彻, 提取复杂问题中的核心点, 最终用递归算法将问题简单化。通过概念和特点的讲解从而领悟到递归思想的构造, 同时举例说明递归算法在树和图中的应用, 同时介绍了折半查找算法中递归思想的应用, 通过已经讲解更深入的掌握递归算法的核心思想。

参考文献

[1]严蔚敏, 吴伟民.数据机构 (C语言) [M].北京:清华大学出版社, 2008.

并行递归算法篇6

一、明确教学目标

新课标指出：“算法部分旨在使学生进一步体验算法思想，了解算法在解决问题过程中的地位和作用，并能从简单问题出发，设计解决问题的算法。”递归算法的教学目标是学会用递归算法的思想分析问题。为了实现该目标，很多教师从递归函数代码的理解出发带领学生学习递归算法，而代码的反复调用很容易给学生理解造成困难。笔者认为指导学生利用递归思想来分析问题是最重要的，理解了递归思想以后，代码的编写就变得相对容易了。

二、学生知识准备

所有的知识都不是空中楼阁，必须有一定的前期知识准备。学生开始学习递归算法前应该已经熟练掌握了顺序结构、分支结构、循环结构，对程序设计语言有了一定的了解，能解决一些有一定难度的程序，有一定的分析问题的能力。而且，学生应该已经掌握了自定义函数，包括函数名、函数参数、函数参数之间的传递等知识。

三、理解递归过程

兴趣是最好的老师，越难理解的知识点越需要抓住学生的兴趣点。对于递归算法的学习，我们可以先让学生玩“汉诺塔”游戏。让他们把塔盘从少到多慢慢增加，一边玩一边总结游戏攻略。通过老师的引导及动画课件，学生应该可以总结出“N个塔盘从A移动到C”的问题可以转换成三个小问题：1.把N-1个塔盘从A移动到B;2.把第N个塔盘从A移动到C;3.把N-1个塔盘从B移动到C。教师只要适时地加以总结：“要想解决复杂问题，可以先把复杂问题转化成简单问题，把问题化解到最小，简单问题解决了，那复杂问题也随之解决。”并给出递归算法的概念：“直接或间接调用本身的算法”，以及递归算法的核心思想：递归分为两个部分，一是递推：大事化小;二是回归：由小及大。当然，教师也可以用“从前有座山”这个大家耳熟能详的故事加以补充说明。

四、把握分析思路

在学生初步了解递归思想后，教师不应急着进入代码的讲解，可以引导学生用递归思想来分析问题，从简单到复杂，从具体到一般。可以从分析求5!开始，分析并总结出求N!的方法。在讲解的过程中，教师可以借助黑板来板书分析思路。(如图)

当分析完5!的求解过程以后，教师可以让学生分析讨论出数学模型，其中包括：递归公式和边界条件

这是一个典型的双分支选择结构语句，可以用IF语句来实现。

五、结合分析完成代码

在学生分析透彻以后，可以让学生试着根据以往的函数知识完成代码的编写。这时可以利用“半成品”的形式，主要是让学生填写递归函数的主体(判断语句)。然后，教师结合代码再次说出递归的过程，学生的印象就很深刻了。这里学生可能会在两个地方出错：1.写成fac (n)=fac (n-1)*n，解释：函数的调用只能在表达式中，而等号是赋值语句，左边只能是变量而不能是表达式。2.函数数据类型和接受返回值的变量数据类型不符，解释：赋值语句等号左右两边数据类型必须相同。

六、适时巩固知识

N!数学模型讨论出以后，学生和教师一起经历了问题分析的过程。这时教师可以适当小结递归概念、递归核心思想、递归边界条件，来帮助学生巩固所学知识。

然后，学生可以用斐波那契数列来进行练习。之所以用斐波那契数列来练习，是因为这个数列学生能很快找到规律，但又因为有两处调用，有一定的难度提高。

当然还是采用从具体到一般的方法，先在学案上分析第5项的数的求法，同时请两位学生到黑板上来分析。再根据分析讨论出递归公式和边界条件(右图为笔者上课时学生书写的学案)。对这道题目的板书分析，以后在总结递归的缺点(重复调用)时也是可以利用的。

七、适当提高应用

在信息技术学科中，学生的能力存在较大差异。而递归算法又在理解上有一定的难度，自然学生达到学习目标的情况也会有所差异。英国现代教育学家沛·西能在《教育原理》中说：“一切教育努力的根本目的应该是帮助学生尽可能达到最高的个人发展。”所以，分层教学在信息技术中会经常运用到。本课内容可以采用难度稍高一点的递归题目作为提高题。笔者在教学的时候采用的是小球自由落体作为分层教学中的提高部分，同时采用小组讨论的形式完成该题的分析。有些教师会让学生编写“汉诺塔”程序，笔者觉得难度太大，会把学生难住，造成学生产生排斥心理。

总之，递归法的教学重点必须落在“算法”上而不是“代码”上。只要学生会用递归算法分析问题，那递归算法的代码就很容易写出来。而只有当学生会用算法的思想分析问题，他们才能真正地体验到算法的魅力，进而爱上《算法与程序设计》这门课。

参考文献

[1]算法与程序设计.教育科学出版社.

用递归与排序算法解决比赛场次问题篇7

编程要求：1)、已知存在一个tennis.in文件，第一行为参加比赛的明星人数N(2≤N≤1000)，从第二行到第N+1行分别为第一个明星到第N个明星期望参加的比赛次数。若文件内容为：3

表示共有三个明星参加比赛，第一个明星期望参加1场，第二个明星期望参加2场，第三个明星期望参加1场

2)、要求输出比赛场次，将输出结果保存于tennis.out文件中。有两种情况：第一种：排不出来，则输出结果为ERROR;第二种：能按照要求排出比赛，则排出比赛的场次，并按每个明星一行的形式输出，第n行为与第n个明星比赛的明星编号，

例：2表示明星1与明星2比赛

1 3表示明星2分别与明星1,3比赛

2表示明星3与明星2比赛

1 问题分析

1)初看这个问题可以用穷举法来解决，但仔细一想由于参加比赛的运动员由2个到1000个不等。如果用穷举法，那么我们应该用多少个循环来处理这个问题呢?看来用简单的穷举法无法处理这个问题。

2)仔细分析这个问题应该是有规律的，为了能保证最大限度地排出比赛场次，我们应首先排出期望参加比赛次数最多明星的比赛场次。第一步：将所有参赛明星按他们期望参加比赛次数的降序进行排列;第二步：将期望参加比赛次数最多明星与其后的其他明星依次安排比赛，若排不完则终止安排比赛，得出结论为“ERROR”，否则继续下一步;第三步：排完期望参加比赛次数最多的明星后，将与其参加比赛明星的比赛次数减1，并将该明星比赛次数置为零;第四步：重复第一至三步直至排完所有明星的比赛场次。结果会出现两种情况：一种是排不出来，输出ERROR;另一种是输出每一位明星的比赛场次。通过以上分析可以将此问题转化为一个排序与递归相结合的问题。

2 编程实现（以下在vb6.0中调试实现）

1)读取tennis.in文件信息(文字部分表示注释)

2)排出期望参加比赛次数最多的明星比赛场次,同时将与其比赛明星的比赛次数减1,并将该明星比赛次数置为零。Private Sub arrange(b()As Integer)

3)按比赛次数对明星信息数组user进行降序排列

4)将结果输出至文件tennis.out中

3 结束语

算法是程序设计的灵魂，一旦算法设计正确，程序代码就显得非常简单了。本程序在算法上充分应用递归与排序，在结构上分别由一个事件过程Form_Load()和三个用户自定义过程arrange()、Sort()、output()组合而成，结构清晰，读者如有兴趣还可以引用此算法解决类似问题。

参考文献

[1]姚志强.利用递归法实现双编号树形数据深度排序的算法[J].长春工业大学学报:自然科学版,2006(4):12.

[2]董萍.改进的快速排序算法与递归[J].安阳工学院学报,2008(6):56.

本文来自古文书网(www.gwbook.cn)，转载请保留网址和出处

同步并行算法01-23