Linear recursion #

Definition. A recursive method is linear recursive if it performs at most one recursive call each time it is executed.

Terminology. The term unary recursion is sometimes used to refer to linear recursive algorithms (as opposed to n-ary recursion).

Hint. A linear recursive algorithm is often easy to transform into an iterative one (i.e. an algorithm that uses only loops).

Example #

int occ(char[] A, char c) {
    return occRec(A, c, 0)
}

int occRec(char[] A, char c, int i) {
    // Base case: the segment under consideration is empty
    if(i == A.length){
        return 0
    }
    // Inductive case.
    // Count the number of occurrences of c in the "suffix" segment A[i+1 .. A.length-1]
    int occInSuffix = occRec(A, c, i + 1)
    return A[i] == c ?
        // If the current character is c, then return this value + 1,
        occInSuffix + 1 :
        // otherwise return this value as it is.
        occInSuffix
}

Tail recursion #

Motivation #

Consider a (not necessarily recursive) method method1 that calls a method method2, for instance:

1
2
3
4
5

method1() {
    ...
    method2()
    ...
}

The execution of method1 is interrupted when it calls method2.

During this interruption, the call stack contains:

method2
method1: 3
<rest of the stack>

Variables that are local to the execution of a method are allocated on the so-called stack memory.

In this example, variables that are local to method1 remain in memory during the execution of method2 (because they may be needed when the execution of method1 resumes). However, if no instruction in method1 needs to be executed after the call to method2, then there is no need to maintain this information in memory.

method1() {
    ...
    method2()
}

In other words, the call stack in this case could be safely be reduced to:

method2
<rest of the stack>

This optimization technique is known as tail-call elimination. Some compilers apply it (but most Java compilers do not).

During the execution of a recursive algorithm, the size of the call stack may become important, therefore also the amount of stack memory required. Therefore identifying calls that may be safely be removed from the stack can significantly reduce memory consumption.

Definition #

A linear recursive method is tail recursive if no instruction in this method can be executed after a recursive call.

A tail recursive algorithm can easily be transformed into an iterative one. This transformation can be viewed as a “manual” form of tail-call elimination.

int occ(char[] A, char c) {
    return occRec(A, c, 0, 0)
}

int occRec(char[] A, char c, int i, int occurences) {
    // Base case: the segment under consideration is empty
    if(i == A.length){
        return 0;
    }
    // Inductive case.
    // If the current character is c, then increment the number of occurrences.
    if (A[i] == c) {
        occurrences++;
    }
    // Recursive call
    return occRec(A, c, i + 1, occurrences)
}

int occ(char[] A, char c) {
    int occurrences = 0
    for (int i = 0; i < A.length; i++) {
        if (A[i] == c) {
            occurrences++
        }
    }
    return occurrences
}

A common strategy to convert a linear recursive method into a tail-recursive one consists in using additional arguments (like the argument occurrences in the above example). These extra arguments are sometimes called accumulators.

Usage #

Linear recursive implementations are not very frequent, because most of them can be easily converted into iterative ones, as illustrated above. Besides, as we explained above, the iterative solution is often more efficient (at least memory-wise) for large inputs.

However, some problems can be easier to solve in a linear recursive form (e.g. as a first attempt). This may also produce code that is easier to read and/or debug.

In particular, it may be the case when manipulating linked lists.

Linked list #

Definition. A linked list is a set of objects organized in a sequence, such that each object (except for the last one) points to its successor.

Equivalently, a linked list is a unary tree (and conversely), i.e. a tree where each node has exactly one (possibly null) child.

For instance:

Terminology.

• the first object in a linked list is often called the head of the list, and
• the rest of the list (i.e. the sublist with the second object as head) is often called the tail of the list.

Example #

Node removeDuplicates(Node head) {
    // Base case: empty list.
    if(head == null) {
        return null
    }
    // Inductive case.
    // Remove all duplicate in the tail.
    Node tailHead = removeDuplicates(head.next)
    // Compare the head with the (possibly new) head of the tail.
    if (tailHead != null && head.label == tailHead.label) {
        // If they have the same label, then return the tail.
        return tailHead
    }
    // Otherwise add the head to the returned list.
    head.next = tailHead
    return head
}