一个递归算法必须包括什么（选择题：一个递归算法必须包括（））

本文目录

• 选择题：一个递归算法必须包括（）
• 递归是怎么回事有没有专门介绍这方面的书啊
• 什么是递归递归有什么用
• 什么是递归编写递归算法需要考虑哪些主要问题

选择题：一个递归算法必须包括（）

一个递归算法必须包括B、终止条件和递归部分。

递归算法在计算机科学中是指一种通过重复将问题分解为同类的子问题而解决问题的方法。

递归式方法可以被用于解决很多的计算机科学问题，因此它是计算机科学中十分重要的一个概念。绝大多数编程语言支持函数的自调用，在这些语言中函数可以通过调用自身来进行递归。

尾部递归：

递归函数在调用自身后直接传回其值，而不对其再加运算。尾部递归与循环是等价的，而且在一些语言（如Scheme中）可以被优化为循环指令。

 因此，在这些语言中尾部递归不会占用调用堆栈空间。以下Scheme程序同样计算一个数字的阶乘，但是使用尾部递归。

递归是怎么回事有没有专门介绍这方面的书啊

　　递归做为一种算法在程序设计语言中广泛应用.是指函数/过程/子程序在运行过程序中直接或间接调用自身而产生的重入现像.
　　程序调用自身的编程技巧称为递归（ recursion）。
　　一个过程或函数在其定义或说明中又直接或间接调用自身的一种方法，它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解，递归策略只需少量的程序就可描述出解题过程所需要的多次重复计算，大大地减少了程序的代码量。递归的能力在于用有限的语句来定义对象的无限集合。用递归思想写出的程序往往十分简洁易懂。
　　一般来说，递归需要有边界条件、递归前进段和递归返回段。当边界条件不满足时，递归前进；当边界条件满足时，递归返回。
　　注意：
　　(1) 递归就是在过程或函数里调用自身;
　　(2) 在使用递增归策略时，必须有一个明确的递归结束条件，称为递归出口。
　　递归算法一般用于解决三类问题：
　　(1)数据的定义是按递归定义的。(Fibonacci函数)
　　(2)问题解法按递归算法实现。(回溯)
　　(3)数据的结构形式是按递归定义的。(树的遍历，图的搜索)
　　递归的缺点：
　　递归算法解题的运行效率较低。在递归调用的过程当中系统为每一层的返回点、局部量等开辟了栈来存储。递归次数过多容易造成栈溢出等。
　　例子：
　　#include 《iostream.h》
　　void move (char getone,char putone)
　　{
　　cout 《《getone《《"--》"《}
　　void hanoi(int n,char one ,char two ,char three)
　　{
　　void move (char getone,char putone );
　　if (n==1)
　　move (one,three);
　　else
　　{
　　hanoi(n-1,one,three,two);
　　move (one ,three);
　　hanoi(n-1,two,one,three);
　　}
　　}
　　void main()
　　{
　　void hanoi(int n ,char one ,char two ,char three);
　　int m ;
　　cout 《《"Input the numberof disker:";
　　cin》》m;
　　cout《《"the steps to moving "《《m《《"diskes
　　:"《《endl;
　　hanoi(m,’A’,’B’,’C’);
　　}
　　第二章 递归
　　2.1 递归的概念
　　2.2 如何设计递归算法
　　2.3 典型例题
　　递归是计算机科学的一个重要概念,递归的方法是程序设计中有效的方法,采用递归编写
　　程序能是程序变得简洁和清晰.
　　2.1 递归的概念
　　1.概念
　　一个过程(或函数)直接或间接调用自己本身,这种过程(或函数)叫递归过程(或函数).
　　如:
　　procedure a;
　　begin
　　.
　　.
　　.
　　a;
　　.
　　.
　　.
　　end;
　　这种方式是直接调用.
　　又如:
　　procedure b; procedure c;
　　begin begin
　　. .
　　. .
　　. .
　　c; b;
　　. .
　　. .
　　. .
　　end; end;
　　这种方式是间接调用.
　　例1计算n!可用递归公式如下:
　　1 当 n=0 时
　　fac(n)={n*fac(n-1) 当n》0时
　　可编写程序如下:
　　program fac2;
　　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(’fac(’,n,’)=’,fac(n):6:0);
　　end.
　　例2 楼梯有n阶台阶,上楼可以一步上1阶,也可以一步上2阶,编一程序计算共有多少种不同的走法.
　　设n阶台阶的走法数为f(n)
　　显然有
　　1 n=1
　　f(n)={2 n=2
　　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.
　　2.2 如何设计递归算法
　　1.确定递归公式
　　2.确定边界(终了)条件
　　练习:
　　用递归的方法完成下列问题
　　1.求数组中的最大数
　　2.1+2+3+...+n
　　3.求n个整数的积
　　4.求n个整数的平均值
　　5.求n个自然数的最大公约数与最小公倍数
　　6.有一对雌雄兔,每两个月就繁殖雌雄各一对兔子.问n个月后共有多少对兔子?
　　7.已知:数列1,1,2,4,7,13,24,44,...求数列的第 n项.
　　2.3典型例题
　　例3 梵塔问题
　　如图:已知有三根针分别用1,2,3表示,在一号针中从小放n个盘子,现要求把所有的盘子
　　从1针全部移到3针,移动规则是:使用2针作为过度针,每次只移动一块盘子,且每根针上
　　不能出现大盘压小盘.找出移动次数最小的方案.
　　程序如下:
　　program fanta;
　　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 of integer;
　　var
　　a:arr;
　　i:integer;
　　procedure quicksort(var b:arr; s,t:integer);
　　var i,j,x,t1:integer;
　　begin
　　i:=s;j:=t;x:=b;
　　repeat
　　while (b》=x) and (j》i) do j:=j-1;
　　if j》i then begin t1:=b; b:=b:=t1;end;
　　while (b《=x) and (i《j) do i:=i+1;
　　if i《j then begin t1:=b:=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.
　　练习:
　　1.计算ackerman函数值:
　　n+1 m=0
　　ack(m,n)={ ack(m-1,1) m《》0 ,n=0
　　ack(m-1,ack(m,n-1)) m《》0,n《》0
　　求ack(5,4)

什么是递归递归有什么用

1、程序调用自身的编程技巧称为递归。递归做为一种算法在程序设计语言中广泛应用。 一个过程或函数在其定义或说明中有直接或间接调用自身的一种方法，它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解，递归策略只需少量的程序就可描述出解题过程所需要的多次重复计算，大大地减少了程序的代码量。递归的能力在于用有限的语句来定义对象的无限集合。一般来说，递归需要有边界条件、递归前进段和递归返回段。当边界条件不满足时，递归前进；当边界条件满足时，递归返回。
2、递归一般的作用用于解决三类问题：
(1)数据的定义是按递归定义的。（Fibonacci函数）
(2)问题解法按递归算法实现。
这类问题虽则本身没有明显的递归结构，但用递归求解比迭代求解更简单，如Hanoi问题。
(3)数据的结构形式是按递归定义的。

什么是递归编写递归算法需要考虑哪些主要问题

递归即 一个函数之间或者间接的调用自己本身，需要注意：
堆栈状态
每个栈上的参数值（即上下文）
退出或者结束条件的设计