小话递归

【 tulaoshi.com - 编程语言 】

　　0:几种数学式的定义:

　　Fibonacci数列:
　　function Fibonacci(n:integer):integer;
　　begin
　　  if n1 then result:=1
　　  else result:=Fibonacci(n-1)+Fibonacci(n-2)
　　end;
　　阶乘,
　　function RankMulti(n:integer):integer;
　　begin
　　  if n1 then result:=1
　　  else result:=RankMulti(n-1)*n
　　end;

　　Ackerman函数:(变态的老外什么都想的出来)
　　function Ackerman(n,m:integer):integer;
　　begin
　　  result:=0;
　　  if (n=1) and (m=0) then result:=2
　　  else
　　  if  (n=0) and( m=1) then result:=1
　　  else
　　  if  (n=2) and(m=0) then result:=n+2
　　  else
　　  if (m=1) and (n=1) then result:=Ackerman(Ackerman(n-1,m),m-1)
　　end;

　　具体的意义我就不罗嗦了，就是个定义而已。涉及到解题思路，就与上面的直接表示略有不同，书上一般都叫作分治法。就是把大问题划分成n个子问题，再用同样的方法去解决..这个东西已经被人们讲烂了，我在讲的话大家要扔砖头了

　　递归的效率使得人们对他的评价褒贬不一。思路清晰使得性能下降其实也算是某种意义上的平衡。不过如果你去考试的话，一般没有很便宜的事情让你用分治法设计一个算法了事。而时间复杂度是必要考虑的，一般情况下要控制在O(n^2)之内.递归的时间复杂度可以用递归方程式求出来。一般情况下，在你的递归式之外的操作时间在O(n)之内的话，可以用递归式内的线性长度为底求递归次数的对数来估计时间复杂度。
　　比如:阶乘的递归式很快，是个线性时间，而Fibonacci数列则是T(n)=T(n-1)+T(n-2)+O(1)的操作，也就是T(n)=2T(n)+O(1),由递归方程式可以知道他的复杂度T(n)是O(n^2)

　　有关复杂性分析可以参考http://algorithm.myrice.com/algorithm/complexity/chapter6.htm
　　本文用到的是方法3套用公式，其中的=可以改写为=或，对于复杂度分析我们总是考虑最坏情况（有些随机算法除外），所以不管写只是个表达方法，本质都是一样的。

　　其实对于复杂度了解清楚就不要总害怕他的低效率了，因为它的复杂度也不总是传说中的指数级。
　　另外用堆栈改写是不能降低复杂度。
　　有些算法是不能用一系列O(1)的算法来迭代改写的。

　　
　　下面是几个分治算法的例子，全部模拟最初的解题思路来递归实现，未经优化。作为抛砖引玉。
　　==========================={CopyRight jinjazz}==========

　　1.求正整数划分的个数:求一个正整数划分为一系列正整数之和有多少不同的划分方法  比如6有11种

　　function DivInteger(n:integer):integer;
　　  function DivMax(n,m:integer):integer;  //求最大子数不大于m的划分个数
　　  begin
　　    result:=0;
　　    if (m=1) or (n=1) then result:=1
　　    else
　　    if mn then result:=DivMax(n,n)
　　    else
　　    if m=n then result:=1+DivMax(n,n-1)
　　    else
　　    if (nm) and (M1) then result:=divMax(n,m-1)+DivMax(n-m,m)
　　  end;
　　begin
　　  result:=DivMax(n,n)
　　end;
　　=========================={CopyRight jinjazz}=============
　　2.求全排列(定义:var PermVar:array[0..4] of Variant;  初始化时可以附任何类型的值)

　　procedure Perm(var JtVariant:array of Variant;k,m:integer;jtList:Tstrings);
　　var i:integer;
　　    procedure swap(var a,b:Variant);
　　    var tmp:Variant;
　　    begin
　　      tmp:=a;
　　      a:=b;
　　      b:=tmp;
　　    end;
　　begin
　　  if k=m then
　　    for i:=k to m do
　　    begin
　　      swap(JtVariant[k],JtVariant[i]);
　　      Perm(JtVariant,k+1,m,JtList);
　　      swap(JtVariant[k],JtVariant[i]);
　　    end
　　  else
　　  begin
　　    jtList.Add('Perm:');
　　    for i:=0 to m do
　　    jtList.Add(JtVariant[i]);
　　    jtList.Add('==================')
　　  end;
　　end;
　　//建议针对不同类型相应的将variant替换掉
　　============================={CopyRight jinjazz}=========
　　3.汉诺塔(虽然经常见但是有多少人亲手写过？)
　　procedure hanoi(n:integer;p1,p2,p3:char;JtList:Tstrings); //个数,盘子标志,输出
　　  procedure move(m:integer;ps,pd:char);
　　  begin
　　    JtList.Add(inttostr(m)+ ' from '+ ps+' to '+pd);
　　  end;
　　begin
　　  if n0 then
　　  begin
　　    hanoi(n-1,p1,p3,p2,JtList);
　　    move(n-1,p1,p2);
　　    hanoi(n-1,p3,p2,p1,JtList);
　　  end;
　　end;
　　//hanoi(3,'a','b','c',memo1.Lines) 
　　==============================={CopyRight jinjazz}========
　　4.快速排序法

　　procedure QuickSort(var SortNum:array of integer;p,r:integer);
　　  procedure swap(var a,b:integer);  //交换
　　  var tmp:integer;
　　  begin
　　    tmp:=a;
　　    a:=b;
　　    b:=tmp;
　　  end;
　　  function partition(var SortNum:array of integer;p,r:integer):integer; //划分
　　  var i,j,x:integer;
　　  begin
　　    i:=p;j:=r+1;
　　    x:=SortNum[p];
　　    while true do
　　    begin
　　      repeat inc(i)
　　      until SortNum[i]x;
　　      repeat inc(j,-1)
　　      until SortNum[j]x;
　　      if i=j then break;
　　      swap(SortNum[i],SortNum[j]);
　　    end;
　　    SortNum[p]:=SortNum[j];
　　    SortNum[j]:=x;
　　    result:=j;
　　  end;
　　var q:integer;
　　begin
　　  if pr then
　　  begin
　　    q:=partition(SortNum,p,r);
　　    QuickSort(SortNum,p,q-1);
　　    QuickSort(SortNum,q+1,r);
　　  end;
　　end;
　　=============================={CopyRight jinjazz}==
　　5.二分查找法.对已排序序列进行查找
　　function BinarySearch(SearchNum:array of integer;x,n:integer):integer;//序列,值,序列长度
　　var left,right,mid:integer;
　　begin
　　  result:=-1;
　　  left:=0;right:=n-1;
　　  while(left=right)do
　　  begin
　　    mid:=(left+right) div 2;
　　    if x=SearchNum[mid] then
　　    begin
　　      result:=mid;
　　      exit;
　　    end;
　　    if xSearchNum[mid] then left:=mid+1
　　                        else right:=mid-1
　　  end;
　　end;
　　=============================={CopyRight jinjazz}=========
　　6.无限位大整数加法(当然有更简便的方法,但这只是个分治法解决问题的思路)
　　function InfiniteAdd(a,b:string):string;
　　var a1,a2,b1,b2,M,D:string;
　　    i,k:integer;
　　begin
　　  if length(a)length(b) then
　　  for i:=1 to length(b)-length(a) do a:='0'+a
　　  else  for i:=1 to length(a)-length(b) do b:='0'+b;
　　  if length(a)=18  then  //int64最大19位，保证不溢出
　　    result:=inttostr(strtoint64(a)+strtoint64(b))
　　  else
　　  begin
　　    k:=length(a) div 2;
　　    a1:=copy(a,1,k);a2:=copy(a,k+1,length(a)-k);
　　    b1:=copy(b,1,k);b2:=copy(b,k+1,length(b)-k);
　　    M:=InfiniteAdd(a2,b2);
　　    D:=InfiniteAdd(a1,b1);
　　    if length(M)length(a2) then
　　      result:=InfiniteAdd(D,'1')+copy(M,2,length(M)-1)
　　    else
　　    begin
　　    if length(M)length(a2) then
　　      for i:=1 to length(a2)-length(M) do M:='0'+M;
　　    result:=D+M;
　　    end;
　　  end;
　　end;

　　============================{CopyRight jinjazz}===============
　　7.无限位大整数整除2（模拟递归过程，没经过优化）
　　function InfiniteDiv2(s:string):string; //这是个O(n)的计算 :-)
　　var i,k,w:integer;
　　    s1,s2,D1,D2:string;
　　begin
　　  if length(s)=17 then
　　  begin
　　    result:=inttostr(strtoint64(s)div 2);
　　  end
　　  else
　　  begin
　　    k:=length(s) div 2;
　　    s1:=copy(s,1,k);s2:=copy(s,k+1,length(s)-k);
　　    D1:=InfiniteDiv2(s1);
　　    D2:=InfiniteDiv2(s2);
　　    if length(D2)k then
　　      for i:=1 to k-length(D2)+1 do D2:='0'+D2;
　　    if byte(s1[length(s1)])mod 2=1  then
　　      D2:=inttostr(strtoint(D2[1])+5)+copy(D2,2,length(D2)-1);
　　    result:=D1+D2;
　　  end;
　　end;
　　=========================={CopyRight jinjazz}======
　　8.无限位数乘法 （模拟递归过程，没经过优化）
　　function InfiniteMulti(a,b:string):string;  //时间复杂度有点高
　　var a1,a2,b1,b2,U,V,X,Y:string;
　　    i,k:integer;
　　begin
　　  if length(a)length(b) then
　　  for i:=1 to length(b)-length(a) do a:='0'+a
　　  else  for i:=1 to length(a)-length(b) do b:='0'+b;
　　  //a*b=a1*b1(补0)+a1*b2(补0)+a2*b1（补0）+a2*b2 不能超过9位

　　  if length(a) mod 2=1 then
　　  begin
　　    a:='0'+a;
　　    b:='0'+b;
　　  end;
　　  if length(a)=9  then  //int64最大19位，保证不溢出
　　    result:=inttostr(strtoint64(a)*strtoint64(b))
　　  else
　　  begin
　　    k:=length(a) div 2;
　　    a1:=copy(a,1,k);a2:=copy(a,k+1,length(a)-k);
　　    b1:=copy(b,1,k);b2:=copy(b,k+1,length(b)-k);
　　    U:=InfiniteMulti(a1,b1);
　　    V:=InfiniteMulti(a1,b2);
　　    X:=InfiniteMulti(a2,b1);
　　    Y:=InfiniteMulti(a2,b2);
　　    for i:=1 to k do
　　    begin
　　      U:=U+'00';
　　      V:=V+'0';
　　      X:=X+'0';
　　    end;
　　    result:=InfiniteAdd(U,V);
　　    result:=InfiniteAdd(result,X);
　　    result:=InfiniteAdd(result,Y);
　　  end;
　　end;