递归算法是啥（递归算法）

本文目录

• 递归算法
• 什么是递归
• 递归是什么意思

递归算法

递归算法
　　 递归算法流程
递归过程一般通过函数或子过程来实现。递归算法：在函数或子过程的内部，直接或者间接地调用自己的算法。
递归算法的特点
　　递归算法是一种直接或者间接地调用自身的算法。在计算机编写程序中，递归算法对解决一大类问题是十分有效的，它往往使算法的描述简洁而且易于理解。 　　递归算法解决问题的特点： 　　(1) 递归就是在过程或函数里调用自身。 　　(2) 在使用递归策略时，必须有一个明确的递归结束条件，称为递归出口。 　　(3) 递归算法解题通常显得很简洁，但递归算法解题的运行效率较低。所以一般不提倡用递归算法设计程序。 　　(4) 在递归调用的过程当中系统为每一层的返回点、局部量等开辟了栈来存储。递归次数过多容易造成栈溢出等。所以一般不提倡用递归算法设计程序。
递归算法要求
　　递归算法所体现的“重复”一般有三个要求： 　　一是每次调用在规模上都有所缩小(通常是减半)； 　　二是相邻两次重复之间有紧密的联系，前一次要为后一次做准备(通常前一次的输出就作为后一次的输入)； 　　三是在问题的规模极小时必须用直接给出解答而不再进行递归调用，因而每次递归调用都是有条件的(以规模未达到直接解答的大小为条件)，无条件递归调用将会成为死循环而不能正常结束。
举例
　　描述：把一个整数按n(2《=n《=20)进制表示出来，并保存在给定字符串中。比如121用二进制表示得到结果为：“1111001”。 　　参数说明：s: 保存转换后得到的结果。 　　n: 待转换的整数。 　　b: n进制（2《=n《=20） 　　void 　　numbconv(char *s, int n, int b) 　　{ 　　int len; 　　if(n == 0) { 　　strcpy(s, ""); 　　return; 　　} 　　/* figure out first n-1 digits */ 　　numbconv(s, n/b, b); 　　/* add last digit */ 　　len = strlen(s); 　　s; 　　int i, base; 　　FILE *fin, *fout; 　　fin = fopen("palsquare.in", "r"); 　　fout = fopen("palsquare.out", "w"); 　　assert(fin != NULL && fout != NULL); 　　fscanf(fin, "%d", &base); 　　/*PLS set START and END*/ 　　for(i=START; i 《= END; i++) { 　　numbconv(s, i*i, base); 　　fprintf(fout, "%s\n", s); 　　} 　　exit(0); 　　} 　　
本段递归算法简析（PASCAL语言）
　　递归是计算机科学的一个重要概念,递归的方法是程序设计中有效的方法,采用递归编写 　　程序能是程序变得简洁和清晰.
一 递归的概念
　　1.概念 　　一个过程(或函数)直接或间接调用自己本身,这种过程(或函数)叫递归过程(或函数). 　　如: 　　procedure a; 　　begin 　　. 　　. 　　. 　　a; 　　. 　　. 　　. 　　end; 　　这种方式是直接调用. 　　又如: 　　procedure c(形参);forward; 　　procedure b; 　　局部说明 　　begin 　　. . 　　c(实参); 　　. . 　　end; 　　procedure c; 　　局部说明； 　　begin 　　. . 　　b; 　　. . 　　end; 　　这种方式是间接调用. 　　例1计算n!可用递归公式如下: 　　fac:=n*fac(n-1) {当n》0时} 　　fac(n)={ 　　fac:=1; { 当n=0时} 　　可编写程序如下: 　　program facn; 　　var 　　n:integer; 　　function fac(n:integer):real; 　　begin 　　if n=0 　　then fac:=1 　　else fac:=n*fac(n-1); 　　end; 　　begin 　　write(’n=’);readln(n); 　　writeln(n,’!=’,fac(n):0:0); 　　end. 　　例2 楼梯有n阶台阶,上楼可以一步上1阶,也可以一步上2阶,编一程序计算共有多少种不同的走法. 　　设n阶台阶的走法数为f(n) 　　显然有 　　n=1 　　f(n)={ 　　f(n-1)+f(n-2) n》2 　　可编程序如下： 　　program louti; 　　var n:integer; 　　function f(x:integer):integer; 　　begin 　　if x=1 then f:=1 else 　　if x=2 then f:=2 else f:=f(x-1)+f(x-2); 　　end; 　　begin 　　write(’n=’);read(n); 　　writeln(’f(’,n,’)=’,f(n)) 　　end.
二 如何设计递归算法
　　1.确定递归公式 　　2.确定边界(终了)条件
三 典型例题
　　例3 汉诺塔问题 　　如图:已知有三根针分别用1,2,3表示,在一号针中从小放n个盘子,现要求把所有的盘子 　　从1针全部移到3针,移动规则是:使用2针作为过度针,每次只移动一块盘子,且每根针上 　　不能出现大盘压小盘.找出移动次数最小的方案. 　　程序如下: 　　program hanoi; 　　var 　　n:integer; 　　procedure move(n,a,b,c:integer); 　　begin 　　if n=1 then writeln(a,’-》’,c) 　　else begin 　　move(n-1,a,c,b); 　　writeln(a,’---》’,c); 　　move(n-1,b,a,c); 　　end; 　　end; 　　begin 　　write(’Enter n=’); 　　read(n); 　　move(n,1,2,3); 　　end. 　　例4 快速排序 　　快速排序的思想是:先从数据序列中选一个元素,并将序列中所有比该元素小的元素都放到它的右边或左边,再对左右两边分别用同样的方法处之直到每一个待处理的序列的长度为1, 处理结束. 　　程序如下: 　　program kspv; 　　const n=7; 　　type 　　arr=array:=b;b:=t1; end 　　until i=j; 　　b:=x; 　　i:=i+1;j:=j-1; 　　if s《j then quicksort(b,s,j); 　　if i《t then quicksort(b,i,t); 　　end; 　　begin 　　write(’input data:’); 　　for i:=1 to n do read(a); 　　writeln; 　　quicksort(a,1,n); 　　write(’output data:’); 　　for i:=1 to n do 　　write(a:6); 　　writeln; 　　end.
本段{递归的一般模式}
　　procedure aaa(k:integer); 　　begin 　　if k=1 then (边界条件及必要操作) 　　else begin 　　aaa(k-1); 　　(重复的操作); 　　end; 　　end;
开放分类：
编程，计算机，算法
***隐藏网址***

什么是递归

程序调用自身就叫做递归。
递归一般用来算一些比较麻烦的算法问题。
递归跟循环的区别，循环注重过程，而递归值注重结果。
简单的来说就是：用循环能实现的，递归一般可以实现，但是能用递归实现的，循环不一定能。因为有些题目①只注重循环的结束条件和循环过程，而往往这个结束条件不易表达（也就是说用循环并不好写）；②只注重循环的次数而不注重循环的开始条件和结束条件（这个循环更加无从下手了）。
要想理解递归一时半会也弄不明白。但是写递归需要记住三个步骤。
1.首先去找临界值，即无需计算，获得的值。
2. 找这一次和上一次的关系
3. 假设当前函数已经可以使用，调用自身计算上一次和这一次的关系。

递归是什么意思

程序调用自身的编程技巧称为递归（ recursion）。递归作为一种算法在程序设计语言中广泛应用。 

一个过程或函数在其定义或说明中有直接或间接调用自身的一种方法，它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解，递归策略只需少量的程序就可描述出解题过程所需要的多次重复计算，大大地减少了程序的代码量。

递归的能力在于用有限的语句来定义对象的无限集合。一般来说，递归需要有边界条件、递归前进段和递归返回段。当边界条件不满足时，递归前进；当边界条件满足时，递归返回。

递归的缺点：

递归算法解题相对常用的算法如普通循环等，运行效率较低。因此，应该尽量避免使用递归，除非没有更好的算法或者某种特定情况，递归更为适合的时候。在递归调用的过程当中系统为每一层的返回点、局部量等开辟了栈来存储。递归次数过多容易造成栈溢出等。

以上内容参考：百度百科-递归