Recursion

For A level computer science the definition of a recursive function is ‘a function that calls itself’.

This is an example of a program with recursive function:

def call_myself():
    print("hello")
    call_myself()


call_myself()

Note that the initial call is outside the function on line 6 but that the function makes a call to itself on line 3.

So here we have a recursive function BUT it’s a pretty bad one. If you were tempted to run it, it would call itself over and over again, printing “hello” each time and eventually giving an error.

A useful recursive function not only calls itself but has to obey a couple more rules.

The 3 rules are:

• the function must call itself (we already know this)
• the function must have a base case – something to make it stop
• the function must move towards the base case

Here’s one that obeys ALL the rules:

def display_numbers(n):
    if n == 10:
        return
    else:
        print(n)
        display_numbers(n+1)

display_numbers(0)

Here we have an initial call to the function on line 8. We have a base case on line 2 which is that if n is 10 we return. We have a general case (the else part) that prints n and then the function calls itself with a new value of n. This moves us towards the base case – n will get 1 bigger each time until it hits the base case where n is 10 and it will stop.