INFORMATION & COMPUTER SCIENCE DEPARTMENT, KFUPM

ICS202 : DATA STRUCTURES

LAB  #05 : Recursion

# Objectives:

1. Writing simple recursive methods.

2. Implementing the find and toString methods of MyLinkedList2 class as recursive methods.

3. Implementing the insertBefore method of MyLinkedList2.Element class as a recursive method.

4. Implementing a recursive method to count the number of non-overlapping occurrences of a given substring in a string.

Download the file lab05.zip and unzip it in the ics202 main folder.  WinZip will automatically create a subfolder lab05 and store some of the files on that folder.  After unzipping, you should have the following files:

Under the ics202.lab05 package:

Complete the recursive method, public void welcomeShabaab(int n), inside the Lab05Task1.java file.  This method should welcome students as in the following example. If the parameter to the method is 3, it should print the following message.

ICS Shabaab, welcome to Lab05.

ICS Shabaab, welcome to Lab05.

ICS Shabaab, welcome to Lab05.

COE Shabaab, welcome to Lab05.

COE Shabaab, welcome to Lab05.

COE Shabaab, welcome to Lab05.

The lines of output would vary similarly according to the parameter n : There will be n lines of  ICS Shabaab, welcome to Lab05.  followed by n lines of COE Shabaab, welcome to Lab05.

Complete the method, public boolean hasLessThan(int[ ] array, int value) and its recursive auxiliary method, inside the Lab05Task2.java file. The method checks whether a given integer array contains a number smaller than a given integer value. Your method should stop immediately it finds a number smaller than value inside the array.

Study the recursive instance method length() of MyLinkedList2 class and its associated auxiliary method. Then solve (a), (b), and (c) below in a similar way:

(a)   Convert the method public Element find(Object obj) of MyLinkedList2 class to a recursive one. Use an auxiliary private method.

(b)   Convert the method public String toString( ) of MyLinkedList2 class to a recursive one such that it returns the string representation of a linked list in the form:

{ValueDatum1  valueDatum2  valueDatum3  . . .  valueDatumN-1   valueDatumN}

Use an auxiliary private method.

(c)   Convert the method public insertBefore(Object obj) of MyLinkedList2.Element class to a recursive one. Use an auxiliary private method.

(d)   Use the given test program TestMyLinkedList2.java to test your recursive methods.