小话递归

0:几种数学式的定义:

Fibonacci数列:
function Fibonacci(n:integer):integer;
begin
if n<1 then result:=1
else result:=Fibonacci(n-1) Fibonacci(n-2)
end;
阶乘,
function RankMulti(n:integer):integer;
begin
if n<1 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 m>n then result:=DivMax(n,n)
else
if m=n then result:=1 DivMax(n,n-1)
else
if (n>m) and (M>1) 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 n>0 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 p<r 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;

标签：

版权申明：本站文章部分自网络，如有侵权，请联系：west999com@outlook.com
特别注意：本站所有转载文章言论不代表本站观点，本站所提供的摄影照片，插画，设计作品，如需使用，请与原作者联系，版权归原作者所有