递归算法及归纳法课件

3.1简介递归算法是由Prof.JohnMcCarthy(麻省理工学院→Stanford大学）提出来的，1970得到应用，那时是出算法的高峰期。今天，几年所有的通用语言都支持递归。递归和归纳法之间的关系非常密切它们以及与它们相关的证明可互相代替。3.2递归例程3.2.1ActivationFrameandRecursiveProcedureCallsThebasicunitofstorageforanindividualprocedureinvocationatruntimeiscalledanactivationframe.Itprovidestoragespacefortheprocedure’slocalvariables,actualparameters,andcompiler“temporaryvariables”,includingthereturnvalue,iftheprocedurereturnsavalue.Italsoprovidesstoragespaceforotherbookkeeping（簿记）needs,suchasreturnaddress,whichtellswhatinstructiontheprogramshouldexecuteafterthisprocedureexits.Thusitprovidesa“frameofreference”inwhichtheprocedureexecutesforthisinvocationonly.Thecompilergeneratescodetoallocationspaceinaregionofstoragecalledtheframestackaspartofthecodethatimplementsaprocedurecall.Thisspaceisreferencedbyaspecialregistercalledtheframepointer,sothatasthisprocedureinvocationexecutes,itknowswhereitslocalvariables,inputparameters,andreturnvaluearestored.Eachprocedureinvocationthatisactivehasauniqueactivationframe.Aprocedureinvocationisactivefromthetimeitisentereduntilitexits.Ifrecursionoccurs,allinvocationsoftherecursiveprocedurethatareactivesimultaneouslyhavedistinctframes.Asaprocedureinvocation(recursiveornot)exits,itsactivationframeisautomaticallyde-allocatedsothatthespacecanbeusedbysomefuturefunctioninvocation.Ahandexecutionofcodethatdepictsthestatesofactivationframesiscalledanactivationtrace.Fibonaccifunctionintfib(intn){

intf,f1,f2;if(n<2)f=n;else{f1=fib(n-1);f2=fib(n-2);f=f1+f2;}returnf;}FIBONACCI递归程程序，其执行（包括激活等）过程见书PP104页。Lemma3.1Inacomputationwithoutwhileorforloops,butpossiblywithrecursiveprocedurecalls,thetimethatanyparticularactivationframeisonthetopoftheframestackisO(L),whereListhenumberoflinesintheprocedurethatcontaineitherasimplestatementoraprocedurecall.Theorem3.2Inacomputationwithoutwhileorforloops,butpossiblywithrecursiveprocedurecalls,thetotalcomputationtimeis(C),whereCisthetotalnumberofprocedurecalls(includefunctioncallsasprocedurecalls)thatoccurduringthecomputation.ActivationTreeExampleandFigureofActivationTreeTheparentofeachothernodeisjustthenodewhoseactivationframewastopoftheframeframestackatthetimethisonewascreated.Thechildrenofeachnodeappearlefttorightintheorderinwhichtheiractivationframeswerecreated.P106Apreordertraversaloftheactivationtreevisitseachactivationframeinorderofitscreation,andthenumberofnodesinthetreeisproportionaltothetotalexecutiontime.3.2.2HintsforRecursion–Method991.procedurep假定理想情况下问题的规模n在0..100之间，即n至多为100.subroutine,p99,除假定理想情况下问题的规模在0..99之间外，其它情况(前置条件、参数、代码等)和p完全一样。3.2.2HintsforRecursion–Method992.写出程序的非递归部分，使之尽可能小。特别注意边界条件3最终，测试，选择一个规模，不必是100，可以是一个小的常数。Recursion注意点Thesubproblemsizeislessthanp’sproblemsize.Thesubproblemsizeisnotbelowtheminimum(0,forthisdiscussion)3.Thesubproblemsatisfiesallotherpreconditionofp99(whicharethesameasthepreconditionofp)例问题：删除表L中第一个出现的元素x，表可能为空表表L中有100，有一个子程序99可用，如果我们能设法使问题即表中的元素个数减小一个，则便可。第二个提示：L可能是空表；还有一种情况，x可能出现在表L中第一个位置程序IntListdelete(IntListL,intx){

IntList

newL,fixedL;if(L==nil)

newL=L;elseif(x==first(L)

newL=rest(L);else{

fixedl=delete99(rest(L),x);

newL=cons(first(L),fixedL);}returnnewL;}

3.3WhatIsaProofxW[A(x)C(x)]几个简单的结论及其证明参见P109双栏证明格式P1104数学归纳法例用数学归纳法证明：P113InductionproofschemaxW[A(x)C(x)]包含下列几个部分：Theproofisbyinductiononx,<descriptionofx>Thebasecaseis…<base-case><Proofofgoalstatementwithbase-casesubstitutedintoit,thatis,C(base-case)>For<x>greaterthan<base-case>,assumethat[A(x)C(x)]holdsforally∈Wsuchthaty<x<Proofofthegoalstatement,C(x),exactlyasitappearsintheproposition>

InductionproofonaRecursiveProcedureDefinition3.2Externalnodesand2-treesAtreethatconsistsofanexternalnodeiscalledaleaf,anditdoesnothaveanysubtrees.Theothertypeofnodeiscalledaninternalnode,itmusthavetwochildren.!?Suchbinarytreesarecalled2-treesbecauseeachnodehastwochildrenornochildren.Definition3.2ExternalpathlengthIna2-treet,theexternalpathlengthoftisthesumofthelengthsofallthepathsfromtherootofttoanyexternalnodet.Thelengthpathlengthofapathisthenumberofitsedges.Alternatively,theexternalpathlengthcanbedefinedinductivelyasfollows:Theexternalpathlengthofaleafis0.Lettbeanonleaf,withleftsubtreeLandrightsubtreeR(eithermaybealeaf).Theexternalpathlengthoftisthe外部长度ofL+外结点数ofL+外部长度ofR+外结点数ofRLemma3.7Lettbeany2-tree.LeteplandmbethevaluesofthefieldeplandextNumrespectively,asreturnedbycalcEpl(t).ThenEplistheexternalpathlengthoft.Misthenumberofexternalnodesint.epl≥mlg(m)EplReturn

calcEpl(TwoTreet){

EplReturn

ansL,ansR;//returnedfromsubtrees

EplReturn

ans=newEplReturn();//toreturnif(tisaleaf){ans.epl=0;ans.extNum=1;}else{

ansL=calcEpl(leftSubtree(t));

ansR=calcEpl(rightSubtree(t));ans.epl=ansLepl+ansR.epl+ansL.extNum+ansR.extNum;

ans.extNum=ansL.extNum+ansR.extNum;}returnans;}用数学归纳法来证明定理推论3.8Theexternalpathlengtheplofa2-treewithninternalnodeshasthelowerbound:epl≥(n+1)lg(n+1)Proof:Every2-treewithninternalnodeshas(n+1)externalnodes.3.5证明程序的正确性3.5.1定义和术语Ablockisasectionofcodewithoneentrypointandoneexitpoint.Aprocedureisablockwithaname,soitcanbecalled.Itusuallyhasparameters,whicharedesignatedeitherasinputoroutput.Noparametersalsoisbothinputandoutput.Afunction,Localdata,Globaldata,Reference3.5.2基本控制结构顺序分支Procedurecall如果没使用循环语句，可以吗？YES！使用递归来取代循环，可以更简单地写任何一个算法。证明正确性前置条件后置条件specification引理3.9Ifallpreconditonsholdwhentheblockisentered,thenallpostconditionholdwhentheblockexits.引理3.10(sequencecorrectness)1.Thepreconditonsoftheblockimplythepreconditionsofblock1.2.Thepostconditonsofblock1implythepreconditionsofblock2.3.Thepostconditonsofblock2implythepostconditionsofblock.

引理3.11(Alternationcorrectness)1.Thepreconditonsoftheblockandthetruthofconditionimplythepreconditionsoftrueblock.2.Thepostconditionoftrue-blockandthetruthofcondition(atthetimetrue-blockisentered)implythepostconditionoftheblock.1.Thepreconditonsoftheblockandthefalsityofconditionimplythepreconditionsoffalse-block.2.Thepostconditionoffalse-blockandthefalsityofcondition(atthetimefalse-blockisentered)implythepostconditionoftheblock.引理3.12(Procedure-Call)1.Thepreconditonsoftheblockimplythepreconditionsofthecalledprocedurewithitsactualparameters.2.Thepostconditionofthecalledprocedurewithitsactualparametersimplythepostconditionoftheblock.Loop-FreeProcedure顺序搜索递归算法intseqSearchRec(int[]E,intm,intnum,intK){if(m>num)

ans=-1;elseif(E[m]==K)

ans=m;else

ans=seqSearchRec(E,m+1,num,K);returnans