Recursion
ITEC 4400/2160 Python Programming for Data Analysis,
Cengiz Günay
(License: CC BY-SA 4.0)
Prev - Errors and Exceptions, Next - Object Oriented Programming
What is recursion
- Reusing a function
- Calling itself
- Similar to a loop
- But not linear, instead it could be exponential
Why recursion
What is the advantage over loops?
- Divide-and-conquer type problems
- Tree search
- Sorting
- etc.
Designing a recursive algorithm
- Do you have a Matroshka doll situation? Identify the part in your problem that repeats and when that happens.
- Identify when the recursion ends. What is the condition that stops it?
Example: Factorial
- Repeating pattern: each time multiply with one less number $$f(n)=n\times f(n-1)$$
- End condition: we stop at 1 $$f(1)=1$$
Classic example: factorial
For demo purposes only, see actual activity on next slide.
Class activity: Solve ONE of these problems
Advanced:
Post your solution link on Piazza.
