java语言程序设计-基础篇--课件(第20章)英文

Chapter20Recursion1MotivationsSupposeyouwanttofindallthefilesunderadirectorythatcontainsaparticularword.Howdoyousolvethisproblem?Thereareseveralwaystosolvethisproblem.Anintuitivesolutionistouserecursionbysearchingthefilesinthesubdirectoriesrecursively.2MotivationsTheEightQueenspuzzleistoplaceeightqueensonachessboardsuchthatnotwoqueensareonthesamerow,samecolumn,orsamediagonal,asshowninFigure20.1.Howdoyouwriteaprogramtosolvethisproblem?Agoodapproachtosolvethisproblemistouserecursion.3ObjectivesToknowwhatarecursivemethodisandthebenefitsofusingrecursivemethods(§20.1).Todeterminethebasecasesinarecursivemethod(§§20.2-20.5).Tounderstandhowrecursivemethodcallsarehandledinacallstack(§§20.2-20.3).Tosolveproblemsusingrecursion(§§20.2-20.5).Touseanoverloadedhelpermethodtoderivearecursivemethod(§20.5).Togetthedirectorysizeusingrecursion(§20.6).TosolvetheTowersofHanoiproblemusingrecursion(§20.7).Todrawfractalsusingrecursion(§20.8).Tounderstandtherelationshipanddifferencebetweenrecursionanditeration(§20.9).4ComputingFactorialfactorial(0)=1;factorial(n)=n*factorial(n-1);n!=n*(n-1)!5ComputeFactorialRunComputingFactorialfactorial(3)6animationfactorial(0)=1;factorial(n)=n*factorial(n-1);ComputingFactorialfactorial(3)=3*factorial(2)7animationfactorial(0)=1;factorial(n)=n*factorial(n-1);ComputingFactorialfactorial(3)=3*factorial(2)=3*(2*factorial(1))8animationfactorial(0)=1;factorial(n)=n*factorial(n-1);ComputingFactorialfactorial(3)=3*factorial(2)=3*(2*factorial(1))=3*(2*(1*factorial(0)))9animationfactorial(0)=1;factorial(n)=n*factorial(n-1);ComputingFactorialfactorial(3)=3*factorial(2)=3*(2*factorial(1))=3*(2*(1*factorial(0)))=3*(2*(1*1)))10animationfactorial(0)=1;factorial(n)=n*factorial(n-1);ComputingFactorialfactorial(3)=3*factorial(2)=3*(2*factorial(1))=3*(2*(1*factorial(0)))=3*(2*(1*1)))=3*(2*1)11animationfactorial(0)=1;factorial(n)=n*factorial(n-1);ComputingFactorialfactorial(3)=3*factorial(2)=3*(2*factorial(1))=3*(2*(1*factorial(0)))=3*(2*(1*1)))=3*(2*1)=3*212animationfactorial(0)=1;factorial(n)=n*factorial(n-1);ComputingFactorialfactorial(3)=3*factorial(2)=3*(2*factorial(1))=3*(2*(1*factorial(0)))=3*(2*(1*1)))=3*(2*1)=3*2=613animationfactorial(0)=1;factorial(n)=n*factorial(n-1);TraceRecursivefactorialMainmethod3SpaceRequiredforfactorial(3)SpaceRequiredforfactorial(2)SpaceRequiredforfactorial(4)4SpaceRequiredforfactorial(3)SpaceRequiredforfactorial(2)SpaceRequiredforfactorial(1)SpaceRequiredforfactorial(4)5SpaceRequiredforfactorial(3)SpaceRequiredforfactorial(2)SpaceRequiredforfactorial(1)SpaceRequiredforfactorial(0)Stack14animationreturn1factorial(4)return4*factorial(3)return3*factorial(2)return2*factorial(1)return1*factorial(0)Step9:return24Step0:executesfactorial(4)Step1:executesfactorial(3)Step2:executesfactorial(2)Step3:executesfactorial(1)Step5:return1Step6:return1Step7:return2Step8:return6Step4:executesfactorial(0)Executesfactorial(4)TraceRecursivefactorialMainmethod3SpaceRequiredforfactorial(3)SpaceRequiredforfactorial(2)SpaceRequiredforfactorial(4)4SpaceRequiredforfactorial(3)SpaceRequiredforfactorial(2)SpaceRequiredforfactorial(1)SpaceRequiredforfactorial(4)5Stack15animationreturn1factorial(4)return4*factorial(3)return3*factorial(2)return2*factorial(1)return1*factorial(0)Step9:return24Step0:executesfactorial(4)Step1:executesfactorial(3)Step2:executesfactorial(2)Step3:executesfactorial(1)Step5:return1Step6:return1Step7:return2Step8:return6Step4:executesfactorial(0)Executesfactorial(3)TraceRecursivefactorialMainmethod3SpaceRequiredforfactorial(3)SpaceRequiredforfactorial(2)SpaceRequiredforfactorial(4)4SpaceRequiredforfactorial(3)SpaceRequiredforfactorial(2)SpaceRequiredforfactorial(1)SpaceRequiredforfactorial(4)5SpaceRequiredforfactorial(3)Stack16animationreturn1factorial(4)return4*factorial(3)return3*factorial(2)return2*factorial(1)return1*factorial(0)Step9:return24Step0:executesfactorial(4)Step1:executesfactorial(3)Step2:executesfactorial(2)Step3:executesfactorial(1)Step5:return1Step6:return1Step7:return2Step8:return6Step4:executesfactorial(0)Executesfactorial(2)TraceRecursivefactorialMainmethod3SpaceRequiredforfactorial(3)SpaceRequiredforfactorial(2)SpaceRequiredforfactorial(4)4SpaceRequiredforfactorial(3)SpaceRequiredforfactorial(2)SpaceRequiredforfactorial(1)SpaceRequiredforfactorial(4)5SpaceRequiredforfactorial(3)SpaceRequiredforfactorial(2)Stack17animationreturn1factorial(4)return4*factorial(3)return3*factorial(2)return2*factorial(1)return1*factorial(0)Step9:return24Step0:executesfactorial(4)Step1:executesfactorial(3)Step2:executesfactorial(2)Step3:executesfactorial(1)Step5:return1Step6:return1Step7:return2Step8:return6Step4:executesfactorial(0)Executesfactorial(1)TraceRecursivefactorialMainmethod3SpaceRequiredforfactorial(3)SpaceRequiredforfactorial(2)SpaceRequiredforfactorial(4)4SpaceRequiredforfactorial(3)SpaceRequiredforfactorial(2)SpaceRequiredforfactorial(1)SpaceRequiredforfactorial(4)5SpaceRequiredforfactorial(3)SpaceRequiredforfactorial(2)SpaceRequiredforfactorial(1)Stack18animationretur