SavCpp8PowerPointsSavitch_ch_14

Chapter14,Recursion,Overview,14.1RecursiveFunctionsforTasks14.2RecursiveFunctionsforValues14.3ThinkingRecursively,Slide14-3,14.1,RecursiveFunctionsforTasks,RecursiveFunctionsforTasks,ArecursivefunctioncontainsacalltoitselfWhenbreakingataskintosubtasks,itmaybethatthesubtaskisasmallerexampleofthesametaskSearchinganarraycouldbedividedintosearchingthefirstandsecondhalvesofthearraySearchingeachhalfisasmallerversionofsearchingthewholearrayTaskslikethiscanbesolvedwithrecursivefunctions,Slide14-5,CaseStudy:VerticalNumbers,ProblemDefinition:voidwrite_vertical(intn);/Precondition:n=0/Postcondition:niswrittentothescreenvertically/witheachdigitonaseparateline,Slide14-6,CaseStudy:VerticalNumbers,Algorithmdesign:Simplestcase:Ifnisonedigitlong,writethenumberTypicalcase:1)Outputallbutthelastdigitvertically2)WritethelastdigitStep1isasmallerversionoftheoriginaltaskStep2isthesimplestcase,Slide14-7,CaseStudy:VerticalNumbers(cont.),Thewrite_verticalalgorithm:if(n10)coutnendl;else/nistwoormoredigitslongwrite_vertical(nwiththelastdigitremoved);coutthelastdigitofnendl;,Slide14-8,CaseStudy:VerticalNumbers(cont.),TranslatingthepseudocodeintoC+n/10returnsnwiththelastdigitremoved124/10=12n%10returnsthelastdigitofn124%10=4RemovingthefirstdigitwouldbejustasvalidfordefiningarecursivesolutionItwouldbemoredifficulttotranslateintoC+,Slide14-9,Display14.1(1),Display14.1(2),TracingaRecursiveCall,write_vertical(123)if(12310)cout123endl;else/nismorethantwodigitswrite_vertical(123/10);cout(123%10)endl;,Slide14-10,Callswrite_vertical(12),resume,Output3,Functioncallends,Tracingwrite_vertical(12),write_vertical(12)if(1210)cout12endl;else/nismorethantwodigitswrite_vertical(12/10);cout(12%10)endl;,Slide14-11,Callswrite_vertical(1),resume,Output2,Functioncallends,Tracingwrite_vertical(1),write_vertical(1)if(110)cout1endl;else/nismorethantwodigitswrite_vertical(1/10);cout(1%10)endl;,Slide14-12,Simplestcaseisnowtrue,Functioncallends,Output1,ACloserLookatRecursion,write_verticalusesrecursionUsednonewkeywordsoranythingnewItsimplycalleditselfwithadifferentargumentRecursivecallsaretrackedbyTemporarilystoppingexecutionattherecursivecallTheresultofthecallisneededbeforeproceedingSavinginformationtocontinueexecutionlaterEvaluatingtherecursivecallResumingthestoppedexecution,Slide14-13,HowRecursionEnds,EventuallyoneoftherecursivecallsmustnotdependonanotherrecursivecallRecursivefunctionsaredefinedasOneormorecaseswherethetaskisaccomplishedbyusingrecursivecallstodoasmallerversionofthetaskOneormorecaseswherethetaskisaccomplishedwithouttheuseofanyrecursivecallsThesearecalledbasecasesorstoppingcases,Slide14-14,InfiniteRecursion,Afunctionthatneverreachesabasecase,intheory,willrunforeverInpractice,thecomputerwilloftenrunoutofresourcesandtheprogramwillterminateabnormally,Slide14-15,Example:InfiniteRecursion,Functionwrite_vertical,withoutthebasecasevoidnew_write_vertical(intn)new_write_vertical(n/10);coutn%100)return(power(2,0-1)*2);elsereturn(1);,Slide14-29,Functioncallends,1isreturned,Tracingpower(2,3),Power(2,3)resultsinmorerecursivecalls:power(2,3)ispower(2,2)*2Power(2,2)ispower(2,1)*2Power(2,1)ispower(2,0)*2Power(2,0)is1(stoppingcase)Seedetailsin,Slide14-30,Display14.4,Section14.2Conclusion,CanyouDeterminetheoutputofthisfunctionifcalledwithrose(4)?introse(intn)if(n0)return(power(x,n-1)*x);elsereturn(1);,Slide14-34,Reviewofpower(cont.),Eachstoppingcasereturnsthecorrectvaluepower(x,0)shouldreturnx0=1whichitdoesintpower(intx,intn)if(n0)return(power(x,n-1)*x);elsereturn(1);,Slide14-35,Reviewofpower(cont.),AllrecursivecallsreturnthecorrectvaluesothefinalvaluereturnediscorrectIfn1,recursionisused.Sopower(x,n-1)mustreturnxn-1sopower(x,n)canreturnxn-1*n=xnwhichitdoesintpower(intx,intn)if(n0)return(power(x,n-1)*x);elsereturn(1);,Slide14-36,Recursivevoid-functions,Thesamebasiccriteriaapplytocheckingthecorrectnessofarecursivevoid-functionCheckthatthereisnoinfiniterecursionCheckthateachstoppingcaseperformsthecorrectactionforthatcaseCheckthatforeachrecursivecase:ifallrecursivecallsperformtheiractionscorrectly,thentheentirecaseperformscorrectly,Slide14-37,CaseStudy:BinarySearch,AbinarysearchcanbeusedtosearchasortedarraytodetermineifitcontainsaspecifiedvalueThearrayindexeswillbe0throughfinal_indexBecausethearrayissorted,weknowa0=a1=a2last,therearenoelementsbetweenafirstandalastsokeyisnotinthissegmentanditiscorrecttosetfoundtofalseIfk=amid,thealgorithmcorrectlysetsfoundtotrueandlocationequaltomidThereforebothstoppingcasesarecorrect,Slide14-48,BinarySearchCheckingtheRecursion(cont.),Foreachcasethatinvolvesrecursion,ifallrecursivecallsperformtheiractionscorrectly,thentheentirecaseperformscorrectlySincethearrayissortedIfkeyamid,keyisinoneofelementsamid+1throughalastifitisinthearray.Nootherelementsmustbesearchedtherecursivecalliscorrect,Slide14-49,BinarySearchEfficiency,ThebinarysearchisextremelyfastcomparedtoanalgorithmthatcheckseachiteminorderThebinarysearcheliminatesabouthalftheelementsbetweenafirstandalastfromconsiderationateachrecursivecallForanarrayof100items,thebinarysearchnevercomparesmorethansevenelementstothekeyForanarrayof100items,asimpleserialsearchwillaverage50comparisonsandmaydoasmanyas100!,Slide14-50,BinarySearchAnIterativeVersion,TheiterativeversionofthebinarysearchmayberunfasteronsomesystemsThealgorithmfortheiterativeversion,showninDisplay14.8,wascreatedbymirroringtherecursivefunctionEvenifyouplananiterativefunction,itmaybehelpfultostartwiththerecursiveapproach,Slide14-51,Display14.8,ProgramExample:ARecursiveMemberFunction,AmemberfunctionofaclasscanberecursiveTheupdatefunctionfromclassBankAccountofDisplay10.6iswillbeoverloadedtocreatearecursiveversionUpdateaddsinterestforaspecifiednumberofyearstoanaccountbalance,Slide14-52,ClassBankAccountFunctionupdate,updateusesoneparameter,years,andthefollowingalgorithm:Ifthenumberofyearsis1,then(/stoppingcase)calltheotherfunctionnamedupdateIfthenumberofyearsisgreaterthan1,thenMakearecursivecalltopostyears1worthofinterestthencalltheotherupdatefunctionforoneyearsinterest,Slide14-53,Display14.9(1),Display14.9(2),FunctionupdateCheckingtheRecursion,ThereisnoinfiniterecursionEachrecursivecallreducesthenumberofyearsbyoneuntilyearsis1,astoppingcaseEachstoppingcaseperformsthecorrectactionOnestoppingcaseisyears=1.Itcallstheotherupdatefunctionwhichwaspreviouslycheckedforcorrectness,Slide14-54,FunctionupdateCheckingtheRecursion(cont.),Forthecasesthatinvolverecursion,ifallrecursivecallsperformcorrectly,theentirecaseperformscorrectly:Whenyears1,therecursivecallcorrectlypostsyears1worthofinterest,thencallstheotherupdatefunctiontopostoneadditionalyearsinterest.Theotherupdatefunctioncorrectlypostsinterestforoneyear.Thentheentireactionforyears1willbecorrect.,Slide14-55,OverloadedFunctions,Thereisnoconfusion(forthecomputer)betweenthetwoversionsofupdateWhentherecursiveversion