Algorithms and Data Structures in an Object-Oriented Framework (“ADSOOF”)

Code for “Lisp Lists and Recursion” section

Note, in the front-end for the code here, in most cases you will be asked to type something in following the prompt “Enter a list of integers” in. What it is expecting here is for the list to be entered in the standard textual representation for Lisp lists. That is, the integers should be separated by commas, and the whole list should have [ at its start and ] at its end. Do not confuse this with what you are asked in other front ends where the prompt is something like “Enter some numbers (all on one line, separated by spaces)”, where you are expected to put spaces between the numbers. The word “list” in the prompt in the front-end code here has the specific meaning of “Lisp list”, it is not just asking for the numbers to be typed with spaces between them.

Although print statements should not be put in code unless they are part of the requirements, it can help to put them in while developing the code for debugging purposes, so long as they are taken out in the final version. It may help you understand recursion better to see some examples with print statements to show you what is happening, so there are some given below.

• LispList.class A .class file enabling you to create and use objects of type LispList<E> for any value of E.
• LispList$Cell.class This file is needed when you have file LispList.class as code in this class uses it, but no direct reference is made to it in this section.
• UseLispLists1.java A program which reads a Lisp list of integers from the screen, written in conventional text format, and prints the sum of its elements.
• UseLispLists2.java A program which has the same effect as UseLispLists1.java, but does the summing of the elements of the Lisp list using a separate method.
• UseLispLists2a.java The same as UseLispLists2, but the sum method is implemented with recursion rather than iteration.
• UseLispLists2b.java The same as UseLispLists2, but shows an example of poor programming practice: mixing recursion with static variables.
• UseLispLists2c.java The same as UseLispLists2, but the sum method is implemented with tail recursion that mimics iteration.
• UseLispLists3.java Demonstrates a static method which takes a Lisp list of any base type and an object of that base type (so it is a generic method) and returns the position of the first occurrence of the object in the list. Includes support code to read in a Lisp list of integers, call the method with the Lisp list and an integer as arguments, and print the result.
• UseLispLists3a.java The same as UseLispLists3, but the position finding method is implemented with recursion rather than iteration.
• UseLispLists3b.java The same as UseLispLists3, but the position finding method is implemented tail recursion that mimics iteration.
• UseLispLists4.java Shows a different way of coding a method with the same effect as that demonstrated in UseLispLists3, and calls it with a list of strings and a string as arguments.
• UseLispLists5.java Demonstrates a generic static method which takes a Lisp list and two objects of its base type, and returns the reverse of the Lisp list with all occurrences of the first base type object replaced by the second.
• UseLispLists6.java Demonstrates a generic static method which takes a Lisp list and two objects of its base type, and returns the Lisp list (not reversed) with all occurrences of the first base type object replaced by the second
• UseLispLists7.java The same as UseLispLists6, but the change method is implemented with recursion rather than iteration.
• UseLispLists8.java Demonstrates a generic static method which takes two Lisp lists and returns the result of joining the second to the back of the first.
• UseLispLists9.java The same as UseLispLists8, but the change method is implemented with iteration rather than recursion.
• UseLispLists10.java Demonstrates a generic static method which takes a Lisp list and returns a boolean indicating whether its length is odd as opposed to even. The method shows a simple use of mutual recursion.
• UseLispLists11.java A better version of UseLispLists10, removes redundant checks.
• UseLispLists12.java Demonstrates a generic static method which reverse a Lisp list, and which is tail recursive.
• UseLispLists13.java Demonstrates a generic static method which is the iterative equivalent of the tail recursive static method in UseLispLists11.
• SortLispLists1.java A method to sort a Lisp list of integers using the insertion sort algorithm, and support code to run it. Uses a separate method to insert each integer into the sorted list.
• SortLispLists2.java (download here). The same as SortLispLists1, but with all the code for the insertion sort algorithm put into a single method.
• SortLispLists3.java The same as SortLispLists1, but with the insert method implemented using recursion rather than iteration.
• SortLispLists4.java The same as SortLispLists1, but with the sort method and the insert method it uses both implemented using recursion.
• SortLispLists5.java A method to sort a Lisp list of integers using the quicksort algorithm, and support code to run it.
• SortLispLists6.java A version of quicksort on Lisp lists of integers, together with support code to run it, which does not require a separate append operation.
• SortLispLists7.java A method to sort a Lisp list of integers using the merge sort algorithm, and support code to run it.
• SortLispLists8.java The same as SortLispLists7, but with the merge method implemented using iteration rather than recursion.

There are version of some of the above methods here with added print statements so you can follow the execution. The print statements will give the values of arguments to method calls, and what is being returned, and in some cases the values of local variables within the calls. After each is printed, you need to type a new line for execution to continue.

• UseLispLists3aw1.java. Demonstrates a static method, implemented with recursion, which takes a Lisp list of any base type and an object of that base type (so it is a generic method) and returns the position of the first occurrence of the object in the list.
  Includes print statements to show values taken and returned by method calls.
• UseLispLists3bw1.java The same as UseLispLists3aw1, but uses tail recursion.
• UseLispLists7w.java A method which takes a Lisp list and two objects of its base type, and returns the Lisp list with all occurrences of the first base type object replaced by the second.
  Includes print statements to show values taken and returned by method calls.
• UseLispLists7w1.java The same as UseLispLists7w, but puts in spaces to show depth of recursion.
• SortLispLists4w.java A method to sort a Lisp list of integers using the insertion sort algorithm.
  Includes print statements to show values taken and returned by sort method calls.
• SortLispLists4w1.java The same as SortLispLists4w, but puts in spaces to show depth of recursion.
• SortLispLists4w2.java The same as SortLispLists4w1 but also includes print statements to show values taken and returned by insert method calls.
• SortLispLists5w.java A method to sort a Lisp list of integers using the quicksort algorithm.
  Includes print statements to show values taken and returned by method calls.
• SortLispLists5w1.java The same as SortLispLists5w, but puts in spaces to show depth of recursion.
• SortLispLists5w2.java The same as SortLispLists5w1, but also has print statements showing intermediate positions.
• SortLispLists6w1.java The same as SortLispLists5w1, but using the version of quicksort without a separate append method.
• SortLispLists7w.java A method to sort a Lisp list of integers using the merge sort algorithm, and support code to run it. Includes print statements to show values taken and returned by method calls.
• SortLispLists7w1.java The same as SortLispLists7w, but puts in spaces to show depth of recursion.
• SortLispLists7w2.java The same as SortLispLists7w1, but also has print statements showing intermediate positions.

Code for recursion with arrayLists

• UseArrayListsRec1.java Finding the biggest integer in an ArrayList of integers, using tail recursion to traverse the ArrayList with a loop index.
• UseArrayListsRec2.java Finding the biggest integer in an ArrayList of integers, using the loop which is the iterative equivalent of the tail recursion in UseArrayListsRec2. Tail recursion is demonstrated, however, in the code which sets up the ArrayList of integers from an array of Strings.
• UseArrayListsRec3.java Finding the biggest integer in an ArrayList of integers, using recursion, but recursion where there is an index which ischanged and the List passed to the recursive call is unchanged.
• UseArrayListsRec4.java Finding the biggest integer in an ArrayList of integers, using recursion and no indexing. Instead, a sublist is passed to the recursive call.
• UseArrayListsRec5.java Finding the biggest integer in an ArrayList of integers, using recursion and no indexing. Here there are two recursive calls taking sublists as their argument.

Last modified: 16 July 2019