Data Structures

Lab #5: Recursion

Objective

During this activity, students will be able to:


Description

This activity must be developed in the pre-assigned teams of two.

NOTE: The files needed to start this lab are available in this tarball file: recursion.tgz. To uncompress, type at the Linux terminal:

tar xzf recursion.tgz

IntList

To solve this lab you must use the IntList (list of integers) class, which is inspired by the lists supported by the Lisp programming language and its dialects. Its interface and implementation are fully provided in the intlist.h and intlist.cpp files. The functions available to manipulate objects of type IntList are described below. You can assume that all these functions have a constant complexity runtime, i.e. \(O(1)\):

Función Descripción

int first(
  const IntList& a
)

Returns the first element of list a. It throws a std::invalid_argument exception if the list is empty. Example:

first(IntList {1, 2, 3})
   1

IntList rest(
  const IntList& a
)

Returns a list which is a copy of list a but without the first element. Throws an std::invalid_argument exception if the list is empty. Example:

rest(IntList {1, 2, 3})
   IntList {2, 3}

IntList cons(
  int value,
  const IntList& a
)

Returns a list which is a copy of list a but with value at the beginning. Example:

cons(1, IntList {2, 3})
   IntList {1, 2, 3}

bool is_empty(
  const IntList& a
)

Returns true if list a is empty, otherwise returns false. Examples:

is_empty(IntList {})
   true

is_empty(IntList {1, 2, 3})
   false

NOTE: In addition to the functions mentioned in the above table, the IntList class implements the following operations with the expected semantics: default constructor, copy constructor, initializer list constructor, destructor, assignment operator (=), equality operator (==), and the to_string member function. Also, the left shift operator (<<) is overloaded in order to print objects of type IntList to output streams such as std::cout.

Functions to Implement

Using C++, implement the functions described below using recursion in each and every one of them. The code must be placed in the recursion.cpp file.

IMPORTANT: Before the definition of each operation you must include a comment that indicates its corresponding time complexity.

Function Description

int size(
  const IntList& a
)

Returns the number of elements contained in list a. Example:

size(IntList {4, 8, 15})
   3

IntList cons_end(
  int value,
  const IntList& a
)

Returns a list which is a copy of list a but with value at the end. Example:

cons_end(16, IntList {4, 8, 15})
   IntList {4, 8, 15, 16}

int sum(
  const IntList& a
)

Returns the sum of all the elements contained in list a. Returns 0 if a is empty. Example:

sum(IntList {4, 8, 15})
   27

IntList duplicate(
  const IntList& a
)

Returns a list where each element of list a appears twice. Example:

duplicate(IntList {4, 8, 15})
   IntList {4, 4, 8, 8, 15, 15}

int last(
  const IntList& a
)

Returns the last element of list a. Assume that a has at least one element. Example:

last(IntList {4, 8, 15})
   15

IntList but_last(
  const IntList& a
)

Returns a list which is a copy of list a but without the last element. Assume that a has at least one element. Example:

but_last(IntList {4, 8, 15})
   IntList {4, 8}

int maximum(
  const IntList& a
)

Returns the largest element contained in list a. Assume that a has at least one element. Example:

maximum(IntList {5, -7, 8, 2, -4})
   8

IntList append(
  const IntList& a,
  const IntList& b
)

Returns a list that is the result of concatenating lists a and b. Example:

append(IntList {4, 8}, IntList {15, 16})
   IntList {4, 8, 15, 16}

IntList repeat(
  int n,
  int value
)

Returns a list where value is repeated n times. Assume that n is greater than or equal to zero. Example:

repeat(5, 2)
   IntList {2, 2, 2, 2, 2}

IntList reverse(
  const IntList& a
)

Returns a copy of list a but in reverse order. Example:

reverse(IntList {4, 8, 15, 16})
   IntList {16, 15, 8, 4}

IntList merge(
  const IntList& a,
  const IntList& b
)

This function should implement the merge algorithm. Returns a list that is the result of interleaving, in ascending order, the elements of the lists a and b. Assume that a and b are in ascending order. Example:

merge(IntList {4, 15, 23, 42},       IntList {8, 16})
   IntList {4, 8, 15, 16, 23, 42}

bool is_prefix(
  const IntList& a,
  const IntList& b
)

Returns true if list a is a prefix of list b, or false otherwise. An empty list is a prefix to any other list. Examples:

is_prefix(IntList {4, 8},
          IntList {4, 8, 15, 16})
   true

is_prefix(IntList {4, 15},
          IntList {4, 8, 15, 16})
   false

IntList insert(
  int value,
  const IntList& a
)

Returns a copy of list a but inserting value in its corresponding place. Assume that a is sorted in ascending order. Example:

insert(16, IntList {4, 15, 23, 42})
   IntList {4, 15, 16, 23, 42}

IntList
  insertion_sort(
    const IntList& a
)

Returns a list with the same elements as list a but in ascending order. List a is unorder. You must use the insert function from the previous problem. Example:

insertion_sort(
    IntList {15, 8, 42, 4, 16, 23})
   IntList {4, 8, 15, 16, 23, 42}

IntList binary(
  int n
)

Returns a list of ones and zeros that represents the value in binary (base 2) of the integer n. For simplicity, the function returns an empty list if n is equal to zero. Assume that n is greater than or equal to zero. Example:

binary(25)
   IntList {1, 1, 0, 0, 1}

Test your code using the unit tests contained in the tests.cpp file (contains a total of 66 assertions).

Deliverables

Place in a comment at the top of the recursion.cpp source file the authors’ personal information (student ID and name), for example:

/*----------------------------------------------------------
 * Lab #5: Recursion
 *
 * Date: 15-Nov-2023
 * Authors:
 *           A01770771 Kamala Khan
 *           A01777771 Carol Danvers
 *----------------------------------------------------------*/

Upload Instructions

To deliver the recursion.cpp file, please provide the following information:

Request PIN

Only one team member needs to upload the file.

Due date is Wednesday, November 15.