Python Programming

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

def countdown(n):
    print(n)
    countdown(n-1)

countdown(10)

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).

1
2
3
4
5
6
7
8

def countdown(n):
    if n <= 0:
        print("Time's up!")
    else:
        print(n)
        countdown(n-1)

countdown(10)

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: since n>0, it will print 3, then calls itself with the argument 2…
  • countdown(n=2) executes: since n>0, it will print 2, then calls itself with the argument 1…
    • countdown(n=1) executes: since n>0, it will print 1, then calls itself with the argument 0…
      • countdown(n=0) executes: since n is not greater than 0 (or n<=0), it will print "Time's up!", and returns None…
    • countdown(n=1) returns None…
  • countdown(n=2) returns None…
• countdown(n=3) returns None…

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.