递归的应用.doc

递 归 的 应 用1、/*递归的经典例子很多，许多基础课本都会讲到“汉诺塔”，这个，就不给你了，上网搜，相当多的。不过，楼上大哥说递归都可以用循环解决，可能是小弟俺所学太少，无法苟同。下面， 是用递归实现批量文件的复制。（当然，你千万别以为我递归的是文件，只是文件名）。之所以要用递归，是因为，文件夹是可以一个套一个，它套了多少个，你不知道。如果不用递归，恐怕只能复制有限层文件夹及文件，且你的代码相当长。这个Copy.java实现的功能是将e盘文件夹1中的所有东西复制并按照原来文件夹的结构放入e:1x中，这与在操作系统中的复制粘贴是一样的。只不过，通过设置数组b的大小，可以有效地控制复制的速度（尤其在复制大文件时可以看出的区别）。*/import java.io.*;public class Copy static String s=e:1x; public void xcopy(File f) for(File f1:f.listFiles() File f2=new File(s+(f1.getPath().replace(e:1,); if(f1.isDirectory() f2.mkdirs(); xcopy(f1); else try FileInputStream fis=new FileInputStream(f1); FileOutputStream fos=new FileOutputStream(f2); byte b=new byte1000; while(fis.available()0) fis.read(b); fos.write(b); fos.flush(); fis.close(); fos.close(); catch(IOException e) System.out.println(Error); public static void main(String args) File f=new File(e:1); new Copy().xcopy(f); 2、汉诺塔问题A B C三个杆子,把B杆的4个碟子(底座最大,倒数第二层次之,倒数第三层次之,第一层碟子最小)全部移到A杆上,最少需移动多少次注:用浅显易懂的方式解答!3. 递归的描述由上面的例子可以看出，一般来说，递归需要有边界条件、递归前进段和递归返回段。当边界条件不满足时，递归前进；当边界条件满足时，递归返回。因此，在考虑使用递归算法编写程序时，应满足两点：1）该问题能够被递归形式描述；2）存在递归结束的边界条件。递归的能力在于用有限的语句来定义对象的无限集合。用递归思想写出的程序往往十分简洁易懂。例2 给出一棵二叉树的中序与后序排列。求出它的先序排列。分析 通过对比二叉树的中序与后序排列，我们可以找出根节点及左右子树。同样的，有可以通过对比左子树的中序与后序排列，找出左子树的根节点可见，该问题能够被递归描述。当找到最后一个根节点时，递归无法再进行下去，这就是递归结束的边界条件。由此可见，递归算法中常常隐含了分治思想。程序如下：program chu01_3; var z,h: string; procedure find(a,b:string); var s,l : integer; begin l:=length(b); if l=1 then Write(b) 边界条件及递归返回段else begin 递归前进段Write(bl); s:=pos(bl,a); if s-10 then find(copy(a,1,s-1),copy(b,1,s-1); 递归左子树if l-s0 then find(copy(a,s+1,l-s),copy(b,s,l-s); 递归右子树end; end; begin Readln(z); Readln(h); Find(z,h); Readln; end.递归的应用1.经典递归例如hanoi塔问题：经典的递归，原问题包含子问题。有些问题或者数据结构本来就是递归描述的，用递归做很自然。2.递归与递推利用递归的思想建立递推关系，如由兔子生崽而来的fibonacci数列。但递推由于没有返回段，因此更为简单，有时可以直接用循环实现。3.分治不少分治方法是源于递归思想，或是递归分解+合并处理。4.回溯规模较小的问题用回溯解决比较自然。注意递归前后要保证现场的保存和恢复，即正确的转化问题。5.动态规划动态规划的子问题重叠性质与递归有某种相似之处。递归+动态修改查表是一种不错的建立动态规划模型的方法。6.其他其他么，就是不好归类。例如表达式处理，排列组合等。附带说一下，用递归来处理打印方案的问题还是很方便的。 例3 求把一个整数n无序划分成k份互不相同的正整数之和的方法总数。分析 这是一道动态规划题，动态方程如下：fi-1,j+fi,j-i+1 （(j mod i=0) and (j div i=1)）fi,j:= fi-1,j (i=j) fi-1,j+fi,j-i （else）s:=f(k,n-k)本题可以用循环来实现递推,也可以考虑用递归求解。主过程如下：方案一：Procedure work(I,j:longint; var s:longint);Var t:longint;BeginIf (i=1) or (j=1) then s:=1Else if (i=0) or (j=0) then s:=0Else beginif (j mod i=0) and (j div i=1) then beginwork(i-1,j,s);t:=s;work(i,j-1,s);s:=s+t+1;endelse if (i=j) then work(i-1,j)else beginwork(i-1,j,s);t:=s;work(I,j-1,s);s:=s+t;end; End;方案二：procedure search(v,w,last:byte);var i:byte;beginif w=0 then inc(count)elseif w=1 thenif v=last then search(0,0,0) elseelse for i:=last to v-1 do search(v-i,w-1,i);end;可以看出，方案一的程序较为冗长，消耗栈空间较大；而方案二较为简洁明了，所用的栈空间也较小，效率较高。因此，使用递归算法也有一个优化问题。算法的简洁与否直接制约了程序的可行性和效率。总结递归使一些复杂的问题处理起来简单明了，尤其在学习算法设计、数据结构时更能体会到这一点。但是，递归在每一次执行时都要为局部变量、返回地址分配栈空间，这就降低了运行效率，也限制了递归的深度。因此，在必要的时候可以只使用递归的思想来求解，而程序则转用非递归的方式书写。递归做为一种算法在程序设计语言中广泛应用.是指函数/过程/子程序在运行过程序中直接或间接调用自身而产生的重入现像.程序调用自身的编程技巧称为递归（ recursion）。 一个过程或函数在其定义或说明中又直接或间接调用自身的一种方法，它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解，递归策略只需少量的程序就可描述出解题过程所需要的多次重复计算，大大地减少了程序的代码量。递归的能力在于用有限的语句来定义对象的无限集合。用递归思想写出的程序往往十分简洁易懂。 一般来说，递归需要有边界条件、递归前进段和递归返回段。当边界条件不满足时，递归前进；当边界条件满足时，递归返回。 注意： (1) 递归就是在过程或函数里调用自身; (2) 在使用递归策略时，必须有一个明确的递归结束条件，称为递归出口。递归算法一般用于解决三类问题：(1)数据的定义是按递归定义的。(Fibonacci函数)(2)问题解法按递归算法实现。(回溯)(3)数据的结构形式是按递归定义的。(树的遍历，图的搜索)递归的缺点：递归算法解题的运行效率较低。在递归调用的过程当中系统为每一层的返回点、局部量等开辟了栈来存储。递归次数过多容易造成栈溢出等。总结应用递归的条基本原则：（1）基本条件：递归过程必须一直存在至少一个不使用递归方法解决的条件。（2）进行方向：任何递归调用都是必须向着“基本条件”的方向进行。（）正确假设：总是假设递归调用是有效的。（4）适度原则：避免使用过多的递归，尤其在效率要求高，而递归调用链过长的情况下。（5）顺序问题：变动递归调用函数的顺序有可能导致整个函数执行顺序的变化。例：一个简单的二分查找程序。#include #include #include using namespace std;int BiSearch(const vector& iv, int& x, int low, int high) if(low high) return -1;int mid = (low + high)/2; if(ivmid x) return BiSearch(iv, x, low, mid -1);return mid;int search(const vector& iv, int& x) return BiSearch(iv, x, 0, iv.size() - 1);int main() vector ivec; cout请输入数字建一个Vector（Ctrl+Zto End）：num) ivec.push_back(num); cin.clear();sort(ivec.be