Lab 5: Recursion

Learning Outcomes

• Use recursion to traverse a list
• Understand and apply recursion in algorithm development
• Develop tests that test boundary conditions

Overview

Video Introduction

In this assignment you will develop comprehensive unit tests for several methods in the List<E> interface and rewrite several methods so that they make use of recursion.

Unit Tests

Write thorough JUnit tests for these methods in the List<E> interface:

• contains(Object target)
• indexOf(Object target)
• get(int index)
• set(int index, E value)
• size()

Recursive Implementations

The repository contains the partial implementations of the ArrayList<E> and LinkedList<E> classes developed in lecture. Using these as a starting point, reimplement the following methods so that no loops are used. Use recursion instead.

• ArrayList.contains(Object target)
• ArrayList.indexOf(Object target)
• LinkedList.contains(Object target)
• LinkedList.indexOf(Object target)
• LinkedList.get(int index)
• LinkedList.set(int index, E value)
• LinkedList.size()

Each method should call a private helper method that does the recursive call. For example, LinkedList.contains(Object target) should call a private recursive version: LinkedList.contains(Object target, Node<E> postion).

Just For Fun

Once you have completed the requirements, you may chose to implement additional methods in the ArrayList and LinkedList classes.

Acknowledgements

This assignment was originally developed by Dr. Chris Taylor.