Lesson 7
Objects and Dictionaries
Chapter 6: Recursion
Recursive countdown timer
So far you have been implementing repetition using iteration (i.e. loops).
Recursion is a completely different way of achieving and thinking about repetition.
Let us try to make recursive functions more useful than what we had in the previous page.
Look at the following code. Predict what it will do. Then copy and run the code!
1 2 3 4 5 |
|
Now that is more useful! When we call countdown()
with 10
, it will print 10
, and then calls itself again with 10-1
which is 9
, which will then print 9
, and then that will call countdown()
again with 9-1
(that is 8
), and so on. So this is essentially a countdown timer…
… that works only if it stops!! Or rather, if it stops without Python giving an error!
The problem now is that while the program counts down, it does not stop! So we have an infinite recursion (which Python fortunately stops).
So we need to define a base condition or base case to stop the recursion once it hits a certain condition.
We will do the obvious: stop the countdown if n
hits 0! This will be the base condition (lines 2-3).
1 2 3 4 5 6 7 8 |
|
This should now work as expected.
Tracing the function calls
In case you haven’t completely got it, let us try to visualise how it works internally.
Let’s say we call countdown(3)
.
Then:
countdown(n=3)
executes: sincen>0
, it will print3
, then calls itself with the argument2
…countdown(n=2)
executes: sincen>0
, it will print2
, then calls itself with the argument1
…countdown(n=1)
executes: sincen>0
, it will print1
, then calls itself with the argument0
…countdown(n=0)
executes: sincen
is not greater than0
(orn<=0
), it will print"Time's up!"
, and returnsNone
…
countdown(n=1)
returnsNone
…
countdown(n=2)
returnsNone
…
countdown(n=3)
returnsNone
…
And we are back to where the original caller was.
Of course, we can easily implement this with a for
loop (as done in an earlier lesson). But there will be cases when it is more elegant and compact to use a recursion over a loop.