It was a dark night, the night was dark and the robbers were in a cave. One robber said to the other “tell us a tale,” and this is the tale he told…

It was a dark night, the night was dark and the robbers were in a cave. One robber said to the other “tell us a tale,” and this is the tale he told…

Recursion is a powerful and fascinating aspect of computer science. It can make seemingly complex problems almost trivially simple and has many applications including working with tree data structures, backtracking, finding permutations, file system navigation and much more besides. It can be a topic which takes some time to understand and even longer to master. Since it is an essential part of all advanced level Computer Science syllabuses, it is a good idea to make a start with it early on so that it can be revisited and understood in more depth later on.

In terms of learning, although it is important to study working examples of recursion, there really is no substitute for spending time trying to code recursive solutions to problems yourself. This article will get you started.

Firstly, type this short Python program into your favourite editor and run it.

def countdown(n):
    if n <= 0:
        print("LIFTOFF!")
    else:
        print(n)
        countdown(n - 1)

countdown(10)

Now go back and see if you can understand the code. In particular, see if you can identify the three laws of recursion :

• A recursive algorithm must have a base case.
• A recursive algorithm must change its state and move toward the base case.
• A recursive algorithm must call itself, recursively.

The base case above is n <= 0. Without a base case and movement towards it at each repeated function call, the program would never end – similar to what happens when you write a while loop with a condition which never becomes true.

In terms of a basic intuitive understanding, the third law is probably the most important:

A recursive function is a function which calls itself.

Now you have seen a recursive function and got some understanding of what they involve, it’s time for some practice. Following are two exercises to help you develop your skill and understanding with recursion. Make sure you give each one a really good try on your own before looking at the solution, in order to get the most out of the exercises.

Exercise 1

Write a function which returns the sum of positive integers up to n (1 + 2 + 3 + ... + n)

Think: what is the base case? How will I move towards the base case? (Hint: by calling the function with a different parameter.)

# Recursive Sum
def sum_recursive(n):
    assert n >= 0
    if n < 1:
        return 0
    return n + sum_recursive(n-1)

assert sum_recursive(5) == 15
assert sum_recursive(10) == 55
</code>

Notes:

• assert is an easy way to do simple testing – if the statement isn’t true you will get an AssertionError, so if you don’t your code is behaving as expected. You could just use print(sum_recursive(5)) for example and check the results yourself.

• We could have called our function just sum but that is already a Python built-in function, so is not a good idea.

Exercise 2

Write a function which multiples two (positive) integers by using repeated addition. For more information on how this works mathematically, see this article.

# Recursive Multiplication
def mult(a, b):
    if a == 1:
        return b
    else:
        return b + mult(a-1, b)

assert mult(3, 6) == 18

These exercises should hopefully give you more experience and confidence with recursion. However, if you are still confused, don’t worry, recursion is a topic that many students find difficult and you may need to be a bit patient with yourself and the topic until understanding comes. In a future article we will look at some slightly more complex recursive algorithms. If you found this article helpful, please let me know in the comments below.

Sharing is caring!