Sue Inn Chng
Image credit:
https://en.wikipedia.org/wiki/Recursion_(computer_science)
The University of 1
Copyright By PowCoder代写 加微信 powcoder
Revision – Functions
– Functions allows you to refer to a set of instructions by its (function) name and it will only execute when its called!
– There are four parts to each function:
1. Thefunctionname(whatit’scalled)
2. Thefunctionarguments(theinformation/variableswepassit) 3. Thereturntype(whatkindofthingisreturnedbythefunction) 4. Thefunctionbody(theactualcodethatdoesthework)
– Function call must be made with the correct function signature. The function name and list of argument types make up the function signature.
The University of 2
Revision – Functions
– Revisit: Lecture 3 – foofighters.py
– Canyoutracetheprogramtoexplainitsoutput?
– True or False?
– Afunctioncancallanotherfunction. – Afunctioncancallitsownself.
The University of 3
– Afunctionisrecursiveifitcallsitselfi.e.itcontainsafunction call to itself.
– ArecursivefunctionisNOTalanguagefeaturebutanother problem solving technique – solve a problem by solving a smaller problem of itself.
– Infiniterecursionhappenswhenaprogramcontinuesmaking recursive calls forever.
– Pythonreportsanerrormessagewhenthemaximumrecursiondepthis reached.
The University of 4
Recursion – Important!
– Allrecursivefunctionsmusthave:
– BaseCase–somewheretostop
– RecurrenceRelation–awaytocontinue
– Sequence of calls must reach its base case, otherwise it goes on making recursive calls forever (infinite recursion), previous example of foo() calls.
– Simpleprogram–countdownandprintBlastoff! – If countdown is 0
• Blastoff! – Else countdown.
The University of 5
countdown(n)
countdown(n)
countdown(n)
countdown(n)
countdown(n)
Example – Blastoff!
Go to: Ed Lesson countdown(n) n The University of 6
countdown(5)
countdown(4)
countdown(3)
countdown(2)
countdown(1)
countdown(0)
Example – Blastoff! Observations
– A new copy of the function is loaded into memory, with its own copies of local variables and arguments.
– When we reached the base case, we have FIVE copies of the function in memory with different arguments.
– End of the function, None is passed back to the previous stack and the memory is released.
– RecursionError when maximum depth exceeded.
– Efficient to a certain extent.
– Not universally applicable technique.
The University of – Recursion
– Go to: Ed Lesson
– Part 1 and Part 2: Read and evaluate recursive programs. – Evaluatethegivenprograms.
• Are these recursive functions?
• Identify the base case.
• Identify the recurrence relation.
• Trace the program for different function calls.
– Part3:Writeownrecursivefunction
– Decomposetheproblemintosimplersolutionofitsownself.
• Identify the base and recurrence relation case conditions.
– Checkwhetherthebasecasecanbereached.
– Ifithasn’tbeenreached,callthesamefunctionwithdifferentarguments.
The University of 8
Practice – Recursive Factorial
– Write a recursive function to calculate the factorial of a positive integer, n.
•𝑓𝑓(𝑛𝑛)=𝑛𝑛! = 𝑛𝑛×(𝑛𝑛−1)!
– Example:
• 𝑓𝑓(5)=5! =5×(4)! • 𝑓𝑓(4)=4! =4×(3)! • 𝑓𝑓(3)=3! =3×(2)! • 𝑓𝑓(2)=2! =2×(1)! • 𝑓𝑓(1)=1! =1
• Go to Ed Lesson The University of 9
– Afunctionisrecursiveifitcallsitself.
– Topreventinfiniterecursion:
– Base case – terminates the function call.
– Recurrence relation – calls to itself with smaller argument.
– Ifyouwriteaninfiniterecursionbyaccident,reviewyourfunction and confirm that there is a base case that does not make a recursive call.
– If there is a base case, check if you can reach this case.
– Recursivefunctionsarewrittenusingconditionals.
– Notalanguagefeature.
– Efficientsolutionsinsomecasesbutnotapplicabletoallsituations.
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