Python Programming

We will talk about a very useful concept in functions. This concept is called recursion, and applies to any programming language that uses functions (so not just Python).

A recursive function is a function that calls itself.

def func(x):
    print(x)
    func(x)

func(5)

Of course, the code above is useless and will result in an error (did you try it?) The function will forever be calling itself without stopping (at least until Python hits the maximum “depth” that the function can call itself). This is an infinite recursion.

So it is obvious that

• we need to do something more useful
• we need a way to stop the recursion

So let’s use recursion more wisely.

First, let us make the function to be a countdown counter.

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

countdown(10)

That is more useful. When we call countdown() with 10, it will print 10, and then it call 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!! At least if it stops without Python throwing an error!

So we need to define a base condition or base case to actually 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.

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

countdown(10)

This should now work as expected.

Let us try to visualise how it works internally.

Let’s say we call countdown(3).

Then:

• countdown() starts with n=3, and since n>0, it will print 3, then calls itself with the argument 2…
  • countdown() starts with n=2, and since n>0, it will print 2, then calls itself with the argument 1…
    • countdown() starts with n=1, and since n>0, it will print 1, then calls itself with the argument 0…
      • countdown() starts with n=0, and since n is not greater than 0 (or n<=0), it will print "Time's up!", and returns…
    • countdown() that had n=1 returns…
  • countdown() that had n=2 returns…
• countdown() that had n=3 returns…

And we are back to where the caller was.

Of course, we can easily implement this with a for loop (as we have already done). But there will be cases when it is more elegant and compact to use a recursion than a loop.

Another example

Here is another common example used to illustrate recursion: computing the factorial of a number \(n! = n \times (n-1) \times (n-2) \times ... \times 3 \times 2 \times 1\).

This time, our function will return a value (an integer).

We are expecting factorial(4) to return 24 (\(4 \times 3 \times 2 \times 1\)).

Can you try to figure out how you would do this yourself before moving on? You may need a pen and paper for this! 📃✒️

It’s sufficient to have a pseudocode scribbled on a paper (or a digital equivalent). Python code is fine too!

Once you are done, I see you on the next page!