RSS订阅递归
概述递归 Top
递归做为一种算法在程序设计语言中广泛应用.是指函数/过程/子程序在运行过程中直接或间接调用自身而产生的重入现象.递归是计算机科学的一个重要概念,递归的方法是程序设计中有效的方法,采用递归编写程序能使程序变得简洁和清晰.。
[编辑本段]定义
一般定义
程序调用自身的编程技巧称为递归（ recursion）。
一个过程或函数在其定义或说明中又直接或间接调用自身的一种方法，它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解，递归策略只需少量的程序就可描述出解题过程所需要的多次重复计算，大大地减少了程序的代码量。递归的能力在于用有限的语句来定义对象的无限集合。一般来说，递归需要有边界条件、递归前进段和递归返回段。当边界条件不满足时，递归前进；当边界条件满足时，递归返回。
注意：
(1) 递归就是在过程或函数里调用自身;
(2) 在使用递归策略时，必须有一个明确的递归结束条件，称为递归出口。
其它定义
递归的另一种定义：
递归，就是用自己的简单情况，定义自己。
在数学和计算机科学中，递归指由一种（或多种）简单的基本情况定义的一类对象或方法，并规定其他所有情况都能被还原为其基本情况。
例如，下列为某人祖先的递归定义：
某人的双亲是他的祖先（基本情况）。 某人祖先的双亲同样是某人的祖先（递归步骤）。 斐波那契数列是典型的递归案例：
Fib(0) = 0 [基本情况] Fib(1) = 1 [基本情况] 对所有n > 1的整数：Fib(n) = (Fib(n-1) + Fib(n-2)) [递归定义] 尽管有许多数学函数均可以递归表示，但在实际应用中，递归定义的高开销往往会让人望而却步。例如：
阶乘(1) = 1 [基本情况] 对所有n > 1的整数：阶乘(n) = (n * 阶乘(n-1)) [递归定义] 一种便于理解的心理模型，是认为递归定义对对象的定义是按照“先前定义的”同类对象来定义的。例如：你怎样才能移动100个箱子？答案：你首先移动一个箱子，并记下它移动到的位置，然后再去解决较小的问题：你怎样才能移动99个箱子？最终，你的问题将变为怎样移动一个箱子，而这是你已经知道该怎么做的。
如此的定义在数学中十分常见。例如，集合论对自然数的正式定义是：1是一个自然数，每个自然数都有一个后继，这一个后继也是自然数。
德罗斯特效应
德罗斯特效应是递归的一种视觉形式。图中女性手持的物体中有一幅她本人手持同一物体的小图片，进而小图片中还有更小的一幅她手持同一物体的图片，依此类推。
[编辑本段]递归应用
递归算法一般用于解决三类问题：
(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');
}
如:
procedure a;
begin
a;
end;
这种方式是直接调用.
又如:
procedure b;
begin
b;
end;
procedure c;
begin
c;
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;
var
a:array[0..10000] of longint;
i:integer;
procedure quicksort(l,r:longint);
var i,j,mid:longint;
begin
i:=l;j:=r;mid:=a[(l+r) div 2];
repeat
while a<mid do inc(i);
while a[j]>mid do dec(j);
if i<=j then
begin
a[0]:=a;a:=a[j];a[j]:=a[0];
inc(i);dec(j);
until i>j;
if i<r then quicksort(i,r);
if l<j then quicksort(l,j);
end;
begin
write('input data:');
readln(n);
for i:=1 to n do read(a);
writeln;
quicksort(1,n);
write('output data:');
for i:=1 to n do write(a,' ');
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)
开放分类
贡献者
