编程中的递归算法

1. 递归算法简单的说法就是自己调用自己。 
    递归过程一般通过函数或子过程来实现，递归方法：在函数或子过程的内部，直接或者间接地调用自己的算法。
但这种算法在高级语言编程中会经常用到，比如：数学函数计算，代码编译以及数据搜索等编程中都会用到。

2. 递归算法解决问题的特点：
(1) 递归就是在过程或函数里调用自身。
(2) 在使用递归策略时，必须有一个明确的递归结束条件，称为递归出口。
(3) 递归算法解题通常显得很简洁，但递归算法解题的运行效率较低。所以一般不提倡用递归算法设计程序。
(4) 在递归调用的过程当中系统为每一层的返回点、局部量等开辟了栈来存储。但递归次数过多容易造成栈溢出等。

3. 递归的一般模式
procedure aaa(k:integer);
begin
    if k=1 then
        (边界条件及必要操作)
    else 
    begin
        aaa(k-1);
       (重复的操作);
    end;
end;

4 例子 楼梯有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.
例子2 快速排序
快速排序的思想是:先从数据序列中选一个元素,并将序列中所有比该元素小的元素都放到它的右边或左边,再对左右两边分别用同样的方法处之直到每一个待处理的序列的长度为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.




					

返回微头条首页

分享到:

喜欢请点赞~

2017-08-17 13:32:30