注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

挽幕斋

小楼东小楼西 旧时梦 触目凝望花丛花是哪年红

 
 
 

日志

 
 

递归  

2010-05-04 23:01:55|  分类: 生活情趣 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

递归做为一种算法在程序设计语言中广泛应用.是指函数/过程/子程序在运行过程中直接或间接调用自身而产生的重入现象.递归是计算机科学的一个重要概念,递归的方法是程序设计中有效的方法,采用递归编写程序能使程序变得简洁和清晰.。

[编辑本段]

数学和计算机科学中,递归指由一种(或多种)简单的基本情况定义的一类对象或方法,并规定其他所有情况都能被还原为其基本情况。

  例如,下列为某人祖先的递归定义:

  某人的双亲是他的祖先(基本情况)。 某人祖先的双亲同样是某人的祖先(递归步骤)。 斐波那契数列是典型的递归案例:

  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[i]<mid do inc(i);

  while a[j]>mid do dec(j);

  if i<=j then

  begin

  a[0]:=a[i];a[i]:=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[i]);

  writeln;

  quicksort(1,n);

  write('output data:');

  for i:=1 to n do write(a[i],' ');

  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) 在使用递归策略时,必须有一个明确的递归结束条件,称为递归出口。

  (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[len] = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ"[n%b];

  s[len+1] = '\0';

  }

  void

  main(void)

  {

  char s[20];

  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 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)={

  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 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[1..n] 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[j]>=x) and (j>i) do j:=j-1;

  if j>i then begin t1:=b; b:=b[j];b[j]:=t1;end;

  while (b<=x) and (i<j) do i:=i+1;

  if i<j then begin t1:=b[j];b[j]:=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;

  评论这张
 
阅读(133)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017