Recursion

Russian dolls are a great visualisation of the concepts behind recursion. Each doll contains another smaller doll, and within that doll is another, and so on until we get to the smallest.

Recursion in the most general sense is when something is defined in terms of itself.

Some other examples of recursion include:

• Snowflakes – each crystal within an individual snowflake has a similar shape to the overall snowflake
• Broccolli – successively smaller parts of the brocolli have the same shape as the biggest part
• Nursery rhymes such as 10 Green Bottles – the overall rhyme is made up of variations of the same verse but each one features successively fewer bottles
• Ancestors – grandmother>great grandmother>great great grandmother>great great great grandmother>great great great great grandmother etc.

Recursion in programming is the defining of a function which refers to itself in the definition.

Take the following pseudo code as an example:

function factorial(n)
    if n=1 then return 1
    else return n*factorial (n-1)
end function

Activity 1

Turn the pseudo code above into a program and test it with values of 1, 3 and 5 (should give 1, 6 and 120 respectively).

The base case

Another example of recursion can be seen in this image. The artist paints what they see, which includes their own hands and everything on their workbench. The inner painting must then also include that detail, and so on at each level until the innermost painting doesn’t need painting because it is too small to be seen. This point where we stop and cannot go any further can be called the base case. It stops us going on forever (called infinite regression).

In the factorial example above, the base case is when n=1. When it is, we return the value 1. If not, the function calls itself, with n-1. We call this the recursive case. The final result will only be returned once all the function calls have received a value back. Each function call feeds a value forward into the next call and this repeats until the base case.

Activity 2

Add a print statement to the code you created in the previous activity which prints out the value of n as soon as the function runs.

Using the value 4 for n, write each step of the calculation in your book to explain what is happening to generate the return value of 24.

Activity 3

Rewrite the factorial program to use a loop instead of recursion. Which is more elegant?

Common recursive algorithms

There are many types of problem that recursion is well suited to. These include:

• binary search
• merge sort
• quick sort
• Fibonnacci terms

Activity 4

Use recursion to create a function which accepts an argument n, and which then returns the nth term in the Fibonacci sequence, where

n = (n-1) + (n-2)

Stack frame

When a subroutine f2 is called from within another subroutine f1 in a low level program, the CPU needs to know where to resume after f2 completes. It knows where to return to thanks to the stack, where the return address is pushed before calling f2.

The same process is true when functions are called in high level languages also. However as well as the return address, the parameters being passed to the function, and return values will also be put on the stack. This whole package of data is known as a stack frame.

A subroutine can call another subroutine, which can itself call another subroutine and so on. In this situation, each call will result in another frame being pushed onto the stack, and we can potentially end up with a lot of frames on the stack. You can imagine that for many layers of call, as can happen with recursive functions, the stack can become full. We call this situation a stack overflow (hence the name of the seminal website).

Activity 5

Here is a skeleton pseudo code algorithm for a recursive binary search with some steps missing.

Build it into a fully implemented working merge sort.

function binarySearch (arr, l, r, x): 
    if r >= l: 
        mid = l + (r - l)// 2

        if arr[mid] == x: 
            # Missing code here 
        else if arr[mid] > x: 
            return binarySearch(arr, l, mid-1, x) 
        else: 
            return binarySearch(arr, mid+1, r, x) 
    else: 
        return -1
end function
# Main program ============================

arr = [  3, 4, 20, 40,60,80 ] 
x=40
result = binarySearch(arr, 0, len(arr)-1, x) 

if result != -1: 
    print ("This line should print something") 
else: 
    print ("This line should print something")

Extension

Use logic to solve the following problem involving Russian dolls. You can work in pairs if a partner is available.

https://www.brainzilla.com/logic/logic-grid/matryoshka-dolls/

Knowledge Check

• Define recursion in general terms
• Define recursion as applied in programming
• List some algorithms that can make use of recursion
• What is an alternative technique to recursion ?
• What is an advantage of recursion?
• What is a disadvantage of recursion?
• Why would it be a bad idea to pass an array by value to a recursive function?