COMP9001
Introduction to Programming
Week 11
Recursion
Presenter: Dr. Hazem El-Alfy
Coordinator: Dr. Karlos Ishac
Some slides are borrowed from the
previous unit coordinator, Sue Inn Chng
Image credit:
https://en.wikipedia.org/wiki/Recursion_(computer_science)
The University of Sydney Page 1
Where are we in the unit?
Week 1 Week 2 Week 3 Week 4 Week 5
Intro Variables Conditionals Containers Loops
Week 6 Week 7 Week 8 Week 9 Week 10
Flow and Advanced Flow File I/O Testing
Classes/Objects
Functions
Week 11 Week 12 Week 13
Recursion Multi-Dim Revision
Arrays
The University of Sydney Page 2
Remember Functions? input output
func
- 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. The function name (what it’s called)
2. The function arguments (the information/variables we pass it)
3. The return type (what kind of thing is returned by the function)
4. The function body (the actual code that does the work)
- Function calls should match the correct function signature. The function name and
list of argument types make up the function signature.
The University of Sydney Page 3
Revision – Functions (W6)
fighter(a,b)
x
a
b
result
foo(a,b)
a
b
result
main()
result
__main__
x
Call stack
The University of Sydney Page 4
Recursion
– A function is recursive if it calls itself i.e. it contains a function
call to itself.
– A recursive function is not a language feature but another
problem-solving technique – solve a problem by solving a
smaller version of itself.
– But how does this work?
– Let's see: Ed Lesson
The University of Sydney Page 5
rec_func(0)
Example – round_trip.py return
rec_func(1)
print('1')
rec_func(2)
print('2')
rec_func(3)
print('3')
rec_func(4)
print('4')
rec_func(5)
print('5')
__main__
Go to: Ed Lesson
rec_func(5)
The University of Sydney Page 6
rec_func(0)
Example – Observations return
rec_func(1)
– A new copy of the function is loaded into
memory, with its own copies of local print('1')
variables and arguments.
rec_func(2)
– When we reached the base case, we have print('2')
FIVE copies of the function in memory with
different arguments. rec_func(3)
print('3')
– At the end of the function, None is passed
back to the previous stack frame and the rec_func(4)
memory is released.
print('4')
– RecursionError occurs when the
maximum stack depth is exceeded. rec_func(5)
– Efficient somehow; prevents infinite recursion. print('5')
– Not a universally applicable technique.
__main__
rec_func(5)
The University of Sydney Page 7
Recursion – Important!
– All recursive functions must have:
– Base Case – somewhere to stop
– Recurrence Relation – a way to continue
– Sequence of calls must reach its base case, otherwise it goes on
making recursive calls forever (infinite recursion)
The University of Sydney Page 8
Calculating the sum of the first n natural numbers
sum(n) = sum(n-1) + n (recursive step)
sum(1) = 1 (base case)
sum(3) = sum(2) + 3
sum(3) = sum(1) + 2 + 3
sum(3) = 1 + 2 + 3
The University of Sydney Page 9
Calculating the sum of the first n natural numbers
The University of Sydney Page 10
Recursive Call
The University of Sydney Page 11
So Why Are We Using Recursion?
Binary Tree Max Finder
The University of Sydney Page 12
