Version: 0.3.38

Recursion

Module:

Recursion

Git Repository:

Lab 03—Recursions

Objectives:

• Play with the concept of recursion

• Implement a linked list in Java

Simple Recursions

We start this lab session with a few small recursive algorithms. Each of them can be written either using iteration of recursion, but we focus here on recursive solutions.

Exercise

Write a program that raises a given value \(v\) to a given positive exponent \(e\). Formally, the task is to write a function \(\mathit{power}(v, e) = v^e\).

1. Identify the base and the recursive cases.

2. Look at the file WarmUp.java, and complete the method named power, using recursion.

3. You can use the PowerTest.java to test your solution.

Solution to Exercise

We can define the power function as the following recurrence:

\[\begin{split}\mathit{power}(v, e) = \begin{cases} 1 & \textrm{if } e = 0 \\ v * \mathit{power}(v, e-1) & \textrm{otherwise} \end{cases}\end{split}\]

We can convert this recurrence as a Java program, as is:

public static int power(int value, int exponent) {
  if (exponent < 0)
     throw new IllegalArgumentException("Negative exponent!");
  if (exponent == 0) return 1;
  return value * power(value, exponent-1);
}

Exercise

Write a program that sums up all the values contained in the given array. Use recursion.

1. Identify the base and the recursive cases.

2. Look at the file WarmUp.java, and complete the method named sum, using recursion.

3. You can use the ArraySumTest.java to test your solution.

Solution to Exercise

To use recursion, I define the sum of the element of the array as being the value in the first cell, to which I add the sum of the remainder of the array. I implement this recursion in a separate method as follows:

public static int sum(int[] array) {
  if (array == null)
     throw new IllegalArgumentException("Cannot sum an null!");
  return doSum(array, 0);
}

private static int doSum(int[] array, int start) {
  if (start >= array.length) {
    return 0;
  }
  return array[start] + doSum(array, start+1);
}

Exercise

We now turn to palindromes, that is, words that are symmetrical such as “kayak”, “madam” or “level”. Write a recursive procedure that checks if a given word is indeed a palindrome.

1. Identify the base and the recursive cases.

2. Look at the file WarmUp.java, and complete the method named isPalindrome, using recursion.

3. You can use the PalindromeTest.java to test your solution.

Solution to Exercise

To check if a word is a palindrome, we check if its first character matches its last one. If that holds, we recurse and go check the remaining characters, that is, the original word minus the first and last characters. This gives us the following recursive procedure:

public static boolean isPalindrome(String text) {
  return checkFrom(text, 0);
}

private static boolean checkFrom(String text, int index) {
  if (index >= text.length() / 2) return true;
  return text.charAt(index) == text.charAt(text.length()-index-1)
         && checkPalindromeFrom(text, index+1);
}

Exercise

Write a recursive procedure that converts a given number into a different base. The base of a number denotes the number of symbols used. For instance, in base 2, we only use two symbols \(\{0,1\}\), and for instance 10 (in base 10) is written ’1010’. Similarly, 5 in base 10 becomes ’12’ in base 3. We can verify that \((1 \times 3^1) + (2 \times 3^0) = 5\).

1. Identify the base and the recursive cases.

2. Look at the file WarmUp.java, and complete the method named toBase, using recursion.

3. You can use the BaseConversionTest.java to test your solution.

Solution to Exercise

One way to convert a given number into another base is to identify the first digit (the rightmost one) by dividing it by the desired base. This gives us a quotient and a remainder. We can map the remainder to a symbol using a static array, which we append to the quotient converted to the same base. That gives us the following Java program:

public static String toBase(int number, int base) {
  if (number < base)
     return SYMBOLS[number];
  return toBase(number/base, base) + SYMBOLS[number%base];
}

Linked Lists

We continue by implementing the sequence ADT as a singly linked list. We implemented the same sequence ADT using arrays in Lecture 2.2.

public abstract class Sequence<T> {
    int length();
    T get(int index) throws InvalidIndex;
    void set(int index, T item) throws InvalidIndex;
    void insert(int index, T item) throws InvalidIndex;
    void remove(int index) throws InvalidIndex;
    int search(T item);
    boolean isEmpty();
}

In this lab session, we will contrast two implementations: One using iteration, and one using recursion.

Using Iteration

We start with the iterative implementation, which is often more “natural”. Figure 1 shows one way to implement the Sequence. The IterativeList class may contain a Node, which, in turn, may refer to another Node, and so on and so forth. The list is thus formed by “linked” nodes. You will find this design in IterativeList.java.

Fig. 2 The IterativeList implements the Sequence ADT and uses the INode class.

Exercise

Implement the insert method using a loop. As we saw during the lectures, you will the getNode method, that finds the i^th node.

1. Implement the getNode method.

2. Implement the insert method.

3. The test cases from IterativeListTest.java can help you find issues in your algorithm.

Solution to Exercise

To insert at a given position I distinguish between two cases: Insertion in front, and insertion further into the list. To insert in front, I first create an initial node and set the head field with it. To insert further, I have to first find the node that precedes the insertion point, create a new node that contains the given item, attach it to the next node, and set the next of previous node with my new node. The code below summarizes this approach:

@Override
public void insert(int index, T item) throws InvalidIndex {
  if (index == 1) {
    head = new INode(item, head);

  } else {
    var previous = getNode(index-1);
    previous.next = new INode(item, previous.next);

  }
}

private INode<T> getNode(int index) throws InvalidIndex {
  if (index < 1) throw new InvalidIndex(index);
  int counter = 0;
  var currentNode = head;
  while (currentNode != null) {
    counter++;
    if (counter == index) return currentNode;
    currentNode = currentNode.next;
  }
  throw new InvalidIndex(index);
}

Exercise

In the worst case, how many comparisons does your algorithm requires? What is the order of growth? Argue.

1. What is the worst case scenario for the insertion?

2. How many comparisons take place in the worst case (a frequency table may help you).

3. Argue for an order of growth

Solution to Exercise

To insert we need to traverse the list up to the insertion point. This is the main body of work, and the problem size is therefore the length of the given list (denoted by \(\ell\)).

In the worst case, we are inserting at the very end of the list, and in this case the work is maximum, because we have to traverse the whole list.

To count the comparisons (see Question [Q:iterative-insert]), we have to count the number of comparisons that take place when we invoke the getNode method. This operation contains a loop, which contains a conditional. The loop condition is evaluated \(\ell+1\) times, and the inner conditional, \(\ell\) times. That gives us a total of \(2\ell+1\). My insert method makes one comparison before it invokes the getNode method, so that gives us a total of \(2\ell+2\) comparisons, in the worst case.

Without detailing the proof, we see that this worst case is linear.

Exercise

In the worst case, how much memory does your solution requires?

Solution to Exercise

Estimating the memory (i.e., the space) requires counting the variables created by the algorithm. As we did while counting comparisons, we have to also look at the getNode method, since it does most of the “heavy lifting” here.

The method getNode creates two variables in all cases. For the insert method, we have to understand both cases to see which one is the worst. If we insert in front, we have to allocate a new Node object, which has two fields, so that is, two pieces of memory. Otherwise, to insert further in the list we still have to allocate a node, but we also need to invoke the getMethod that declares two variables. That is 4 cells in total.

Overall, we see that this is constant, because it does not depends on the problem size, which is the length of the list.

Using Recursion

We will now use recursion to implement the same linked list. Look at the file RecursiveList.java. The length method is a simple example, shown below:

@Override
public int length() {
    return lengthFrom(head);
}

private int lengthFrom(RNode<T> start) {
    if (start == null)
        return 0;
    return 1 + lengthFrom(start.next);
}

Often, recursive algorithms need to accept more arguments than their iterative counterpart. That’s the role of the lengthFrom operation, which embodies the actual recursive implementation. The length operation directly calls it.

Exercise

By taking inspiration on the length method, implement the insert operation in a recursive manner. Here are questions that might help to guide you.

1. Can you identify self-similar sub problems. The structure of the linked list may help you.

2. What are the base cases?

3. What are the recursive cases?

Solution to Exercise

A list is recursive by definition. It is just an item followed by another shorter list. We can use this definition to build a recursive implementation of the insert function. Insertion in 3^rd position in a list of 5 items, is the same as inserting in the 2^nd position in the sub-sequence starting at the 2 position. Consider these examples:

• Inserting Z at the 3^rd position of a sequence \(s=(A, B, C, D)\), is the same skipping A, and insert Z at the 2^nd position of the sequence \(s'=(B,C,D)\).

• Inserting Z at the 5^th position of a sequence \(s=(A, B, C, D)\), is the same skipping A, and insert Z at the 4^th position of the sequence \(s'=(B,C,D)\).

The idea if to create a function that insert after a given position, but from a given start node.

private void insertAfter(RNode<T> start, int index, T item) {

}

There are two base cases:

• If we insert a the beginning of the list, we need to update the head field. This case occurs when the given index is zero.

• If we have found the node that precedes the insertion points, we need to create a new node and wire it into the list. This case occurs when index is 1.

Finally, when index is greater than 1, it means that we have not yet found the node that precedes the insertion point, and we must place a recursive call, passing in the node that follows the current one, and the given index decremented by one.

The following piece of code gives illustrates this idea:

@Override
public void insert(int index, T item) throws InvalidIndex {
    if (index < 1)
        throw new IllegalArgumentException("Invalid index");
    insertAfter(head, index - 1, item);
}

private void insertAfter(RNode<T> start, int index, T item) throws InvalidIndex {
    if (index == 0) {
        var newNode = new RNode<T>(item, start);
        head = newNode;

    } else if (index == 1) {
        var newNode = new RNode<T>(item, start.next);
        start.next = newNode;

    } else if (index > 1) {
        insertAfter(start.next, index - 1, item);

    } else {
        throw new IllegalArgumentException("Invalid Index");

    }

}

Exercise

In worst case, how many comparisons will your recursive insertion takes?

1. Identify the worst case. What is it?

2. Count the comparisons needed for each base and recursive cases.

3. Write down the number of comparisons as a recurrence relationship.

4. Solve this recurrence.

Solution to Exercise

The worst case occurs when one tries to insert an item at the very end of the list. For instance, given a sequence \(s=(A,B,C,D)\), the worst case would be to insert in 5^th position.

What happen in this worst case. Only two cases of the algorithm are exercised:

• The base case where we have found the node that precedes the insertion point. In that case, we execute two comparisons.

• The recursive case, where we propagate the insertion to the next node. In that case, we execute 3 comparisons, plus the comparisons incurred by the recursive call.

We can formulate that using the following recurrence relationship \(t(\ell)\), where \(\ell\) denotes the length of the sequence.

\[\begin{split}t(\ell) = \begin{cases} 2 & \textrm{if } \ell == 1 \\ 3 + t(\ell-1) & \textrm{otherwise} \\ \end{cases}\end{split}\]

We can expand the expression \(t(\ell)\) to see what pattern it yields:

\[\begin{split}t(\ell) & = 3 + t(\ell-1) \\ & = 3 + \left( 3 + t(\ell-2) \right) \\ & = 3 + \left( 3 + \left[ 3 + t(\ell-3) \right] \right) \\ & = \underbrace{3 + 3 + \ldots + 3}_{\ell-1 \textrm{ times}} + t(1) \\ & = 3 (\ell-1) + 2 \\ & = 3\ell - 1\end{split}\]

Exercise

In the worst case, how much memory will it takes? Remember to account for the call stack.

Solution to Exercise

Just as we did for counting comparisons, we have to count the pieces of memory that are allocated. Each call to insertAfter requires storing three input arguments

That gives us the following recurrence relationship \(m(\ell)\) where \(\ell\) denotes the length of the sequence.

\[\begin{split}m(\ell) = \begin{cases} 0 & \textrm{if } \ell = 1 \\ 3 + t(\ell + 1)& \textrm{otherwise} \\ \end{cases}\end{split}\]

By solving this recurrence, we obtain \(m(\ell) = 3(\ell-1);\), which is linear. By contrast with the iterative approach, a recursive algorithm consumes memory on each call.

Benchmark

Let see now is theory matches practice. To get some concrete evidence, we will try to insert items in both an IterativeList and in a RecursiveList. Take a look at the file Benchmark.java, which implements the above scenario.

Exercise

Run the benchmark on your machine. What result do you get. To run the benchmark, you can use the command:

$ java -cp target/lab03-0.1-SNAPSHOT.jar \
           no.ntnu.idata2302.lab03.Benchmark

Solution to Exercise

On my machine, I obtain the following:

$ java -cp target/lab03-0.1-SNAPSHOT.jar \
           no.ntnu.idata2302.lab03.Benchmark
Iterative List: 100000 item(s) inserted.
Recursive List: 23723 item(s) inserted. (error)

Exercise

Why do you think happen to RecursiveList? Why is it underperforming?

Solution to Exercise

Most languages and OS limit the size of the call stack, so that it cannot grow indefinitely. Looking at the code of the benchmark, we are actually catching a StackOverflowError which, in Java, indicates that the program has used all the memory allowed for the call stack. That is often the main problem of recursive algorithms: They consume more memory. We will see further in the course, method to avoid that in some cases.