[SOLVED] CS List 1 List 2

List 1 List 2

Copyright By Assignmentchef assignmentchef

Recursive Applications
The University of 1

Recursive Solution
Recursivesolutionconditionalsandfunctioncallstoitself.
Towriterecursivesolution:
Decomposetheproblemintosimplersolutionofitsownself.
Identify the base case and recurrence relation.
Checkwhetherthebasecasecanbereached.
Ifithasntbeenreached,callthesamefunctionwithdifferent arguments.
Thealternativetoarecursivesolutionisaniterativesolution: Iterativesolutionwhileorforloops
OurexamplesiterativeBlastoff!
The University of 2

Recursive Applications
Factorial
Fibonacci
Binomialcoefficients
Traverseaniterableobject: Summation
The University of 3

Writeafunctionthatsumsallelementsinaniterableobject using a recursive solution.
Iterationeasypeasy!
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: assignmentchef QQ: 1823890830 Email: [email protected]