Scheme_2_Efficiency

《Scheme_2_Efficiency》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、Lecturecontents•Inthislecturewewilllookat:•Theprocessesgeneratedbytheevaluationofrecursivedefinitions(A&S1.2)–“Iterative”vs“recursive”definitions.EfficiencyandFormulatingAbstractions–EfficiencywithHigherOrderProcedures•Formulatingabstractionswithhigher-or

2、derprocedures(A&S1.3)Abelson&Sussman&Sussman–proceduresasargumentssections:(firstpart)1.2&(firstpart)1.3–constructingproceduresusinglambda–proceduresasgeneralmethods–proceduresasreturnedvalues•WewilldefertheunderlinedtopicsuntilnextlectureAdvancedProgramm

3、ingParadigmsAdvancedProgrammingParadigms©2002TheUniversityofAdelaide/1.0IntroScheme-3/Slide1©2002TheUniversityofAdelaide/1.0IntroScheme-3/Slide2WhyunderstandingprocessisimportantExample:Factorial•Whenwritingaprogram,itisimportanttobeableto•Recursivedefini

4、tionscanhavedifferentefficiencies.visualisewhattheprogramwilldowhenitruns.•Considerthefollowingdefinitionoffactorial:•Withoutthisknowledgeyoucannottellifaprogramdoes(define(factorialn)whatyouwantittodo.(if(=n1)1–ordoesitsjobefficiently!(*n(factorial(-n1))

5、)))•Recursivedefinitionsdescribehowacomputationalprocess•Thisdefinitionmakesonerecursivecalltofactorialandthengetsfromonestagetothenext.multipliestheresultbyn.–Itdescribeslocalprocessing.•Thevalueofnmustberecordedsomewheresoweknow•You,astheprogrammer,need

6、tounderstandhowthesewhattomultiplybywhentherecursivecall:factorial(n-1)elementsoflocalprocessingarejoinedtogethertoformareturns.globalprocess.–Wemustalsorememberthatthenextthingwehavetodo,afterreturning,ismultiplication.AdvancedProgrammingParadigmsAdvance

7、dProgrammingParadigms©2002TheUniversityofAdelaide/1.0IntroScheme-3/Slide3©2002TheUniversityofAdelaide/1.0IntroScheme-3/Slide4Example:Factorial(cont’d)Amoreefficientfactorial•Sampleevaluation:•Amoreefficientversionoffactorial:(define(factorialn)(fact-iter1

8、1n))(define(fact-iterproductcountermax-count)(if(>countermax-count)product(fact-iter(*counterproduct)(+counter1)max-count)))•fact-iterdoesnotperformanycomputationaftertherecursivecall–Noextrainformationtoremember.–T