Lab #5: Recursion

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

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}