List 1 List 2
Copyright By PowCoder代写 加微信 powcoder
Recursive Applications
The University of 1
Recursive Solution
– Recursivesolution–conditionalsandfunctioncallstoitself.
– Towriterecursivesolution:
– Decomposetheproblemintosimplersolutionofitsownself.
• Identify the base case and recurrence relation.
– Checkwhetherthebasecasecanbereached.
– Ifithasn’tbeenreached,callthesamefunctionwithdifferent arguments.
– Thealternativetoarecursivesolutionisaniterativesolution: – Iterativesolution–whileorforloops
– Ourexamples–iterativeBlastoff!
The University of 2
Recursive Applications
– Factorial
– Fibonacci
– Binomialcoefficients
– Traverseaniterableobject: – Summation
The University of 3
– Writeafunctionthatsumsallelementsinaniterableobject using a recursive solution.
– Iteration–easypeasy!
– Recursion – can you do it?
• Identify the base case – somewhere to stop
• Identify the recurrence relation – a way to continue
The University of 4
5 + 10 + 15 + 20 + 1
– Writeafunctionthatsumsallelementsinaniterableobject using a recursive solution.
– Identify the base case – ???
– Identify the recurrence relation – rsum(ls[1:])
5 + 10 + 15 + 20 + 1
– Go to Ed Lesson. The University of Sydney
Basic Search Algorithm – Iterative Solution
– Simple function: search(item, a_list)
– IterativeAlgorithm:
– Traverseeachelementintheiterableobject,a_list
• Check if an element has the same value as item. – If yes, return True
– Example: “Fish”
The University of 6
Basic Search Algorithm – Recursive Solution
– Functionsearch(item,a_list)
– Algorithm:
– Ifthefirstelementhasthesamevalueasitem,returnTrue
– Else,searchremainingiterableobject(excludingfirstelement)untilitis found or a_list is empty.
– Example: “Fish”
The University of 7
Basic Search Algorithm – Observations
– Whathappenswhenweneedtosearchthrough1000 elements for occurrence of 5, 400 and 1000?
– Iteration works for all cases.
– Recursion works only for small numbers.
– Isthereamoreefficientwaytosearchwithoutvisitingeach element?
The University of 8
Binary Search Algorithm
– Assumethelistissortedfromsmalltobig
– Check the middle element in the list
– If the search item(x) is same as middle element, return True
– If the search item(x) is smaller than middle element, search lower half
– Ifthesearchitem(x)isbiggerthanmiddleelement,searchtheupperhalf
– Go to Ed Lesson. The University of 9
– Recursivefunctionshaveabasecaseandarecurrencerelation. – Summationusingrecursion
– Basicsearchusingrecursion
– Binarysearchusingrecursion
– Recursionisnevernecessary:thealternativeisiteration.
– range(start, stop) sequence type:
– https://docs.python.org/3/library/stdtypes.html#range – Generatesintegersfromstarttostop-1
The University of 10
Reading This Week
– Chapter5.Recursion.Downey,A.B.(2015).ThinkPython:How to Think Like a Computer Scientist (2e ed.). O’ , Incorporated.
– Basicsofrecursion.
– Chapter2.3.Recursion.Sedgewick,R.,Wayne,K.,&Dondero, R. (2015). Introduction to programming in Python: An interdisciplinary approach. Addison- .
– Examplesofrecursionapplications.
The University of 11
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com