In its most common form, recursion usually refers to recursive functions. A recursive function is a function which calls itself. The effect of this is that the exact same sequence of operations is performed repeatedly. The purpose of this is the same as the usual imperative iteration constructs such as for and while loops, but the effect is quite different.

A recursive function will always consist of two things – A base case and a recursive case.

The base case – Earlier I defined a recursive function to be a function which calls itself. Upon seeing a recursive function for the first time, the instinctive reaction of many is to exclaim “that shouldn’t work!” – it seems counter-intuitive to think that if the function calls itself that it will ever stop calling itself. The base case is the part which makes recursion actually work by forcing it to stop at the necessary point. Leaving out the base case will almost certain result in a function which never terminates.

The recursive case – The recursive case is the part in which the function actually calls itself with diminished input. The function must not call itself with the exact same input again, otherwise it will continue doing so forever! The function should be reducing the input and thus be moving closer to the base case.

To combine these two concepts, here is a small example:

Let’s say we wish to define a function called “count” which when given a list of items returns the number of items in that list. The following is a rough psuedo-code implementation of this function.

function count( list )
    if list is empty then
        return 0
    endif

    if list is not empty then
        return 1 + count(tail(list))
    endif

I will step through line by line and explain what is occurring.
The first line defines a function “count” which takes a parameter called “list”.
Lines 2-4 check if the list is empty and if so return 0 – this is our base case which ensures that our function will terminate when it has no more input.
Lines 5-7 check if the list is not empty and if this is the case, it calls the function again. I have made use here of a function called “tail” which returns all elements in a list except the first one. For example, given a list [1, 2, 3, 4, 5] tail([1, 2, 3, 4, 5]) would return [2, 3, 4, 5]. This is the recursive case, and the “tail” function is used to reduce our input, bringing it closer and closer to the base case. 1 is then added to the result of the “count” function being called on all but the first element of the list. The way this recursion “unwinds” is like this:

count([1,2,3,4]) = 1 + count([2,3,4])
count([2,3,4] = 1 + count([3,4])
count([3,4]) = 1 + count([4])
count([4]) = 1 + count([])
count([]) = 0

Calling count with the empty list ([]) triggers the base case and halts any further recursive calls to count. The recursion is then evaluated by replacing each recursive call with its result:

count([]) = 0
count([4]) = 1 + 0 = 1
count([3,4]) = 1 + 1 = 2
count([2,3,4] = 1 + 2 = 3
count([1,2,3,4]) = 1 + 3 = 4

4 is the correct answer – it is the length (number of elements) of the list [1,2,3,4].

1. What is Recursion?
2. Why is recursion useful?
3. Recursion by example