Recursive Functions

Dr Ian Cornelius

Hello

Hello (1)

Learning Outcomes

Understand the concept of recursion and recursive functions
Practice and implement recursive functions

Recursive Functions

Recursive Functions (1)

Recursion is concerned with a function calling itself, either:
- directly: the function contains a call to itself
- indirectly: the function contains a call to another function, which in turn calls the recursive function
There must be some sort of condition to ensure this process can be stopped
- otherwise, known as base case

def recursion_fun():
    ...
    recursion_fun()
    ...

recursion_fun()

You should already be familiar with functions and how they operate in Python. We know that functions are able to call other functions, however, it is also possible for a function to call itself, and this is known as recursive functions.

On the screen is a simple example of how a recursive function would be laid out. You would initially declare a function by using the def keyword, and inside the body of that function would be some logic and then a further call to that function.

Recursion can happen either directly or indirectly. When we use the term directly, it is concerned with a function containing a call to itself directly; whereas the term indirectly is concerned where there is a condition to call another function, which in-turn will call the recursive function. When you call a recursive function in the main body of the script, it will continue calling itself until a condition has been met which will terminate the process; this is known as a base-case.

Recursive Functions (2)

Infinite Recursion

When a function calls itself, then the called execution will also call a further execution and so on
- this would result in an infinite number of calls made, known as infinite recursion
To avoid this, the recursive function must be carefully constructed
Ensure at some stage that the function can terminate without calling itself

Recursive Functions (3)

Why use Recursion?

Recursive functions can make code look clean and elegant
Generating sequences is easier with recursion instead of nested iteration
Complex tasks can be broken down into simpler sub-problems

But…

Following the logic of a recursive function can be difficult
Recursive calls are inefficient and can take up a lot of memory and time
Recursive functions can be difficult to debug

Recursive Functions (4)

Example: Factorial

A simple example of recursion is the factorial function, \(f(n) = n!\)
When called with a positive integer, it will call itself by decreasing the number
Each function will multiply the number with the factorial of the number below it, until it is equal to one

def factorial(x):
    if x == 1:
        return 1
    return x * factorial(x - 1)

factorial(5) -> 120

Let’s have a look at an example of a recursive function. On the screen we have a function called factorial. When the function is called with a positive integer it will multiply the value of x with the number before it. This is achieved through recursion by calling the function once again in the return statement.

When we call this function with a value of five, then its execution will perform: 5 * 4 * 3 * 2 * 1. However, as soon as x becomes equal to one, the recursion function will return the value one and not the recursive call. This is our terminating statement, and it is at this conditional check that the recursive function is broken.

Recursive Functions (5)

Example: String Reversal

Another example of a recursive function is reversing a string
When met with an empty string, the process is terminated
However, if the list contains multiple elements, then a pattern needs to be found
- the first character of the string is concatenated to the end of the remaining characters
- this is repeated until the end of the string, i.e. when it is empty

def reverse_string(s):
    if s == "":
        return s
    return reverse_string(s[1:]) + s[0]

reverse_string(‘hello’) -> olleh

Another example of a recursive function is the reversing of a string.

The function on the screen accepts a parameter called s and this is our target string that will be reversed. As always, we need some form of a conditional check to be applied to provide a base-case for when our recursive function should terminate. In this instance, I have chosen to end the function when the string is empty.

If the string was empty, we would return just the empty string and not call our function again, thus terminating the recursion. However, if characters were still present in the string, then it will continue to call our function by taking the first character of the string and appending it to the end of it.

Goodbye

Goodbye (1)

Questions and Support

Questions? Post them on the Community Page on Aula
Additional Support? Visit the Module Support Page
Contact Details:
- Dr Ian Cornelius, ab6459@coventry.ac.uk