Práctica #6: Recursión

int first(
  const IntList& a
)

Devuelve el primer elemento de la lista a. Lanza la excepción std::invalid_argument si la lista está vacía. Ejemplo:

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

IntList rest(
  const IntList& a
)

Devuelve una lista con los mismos elementos que la lista a excepto el primero. Lanza la excepción std::invalid_argument si la lista está vacía. Ejemplo:

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

IntList cons(
  int value,
  const IntList& a
)

Devuelve una lista con los mismos elementos que la lista a pero con value al inicio. Ejemplo:

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

bool is_empty(
  const IntList& a
)

Devuelve true si la lista a está vacía, de lo contrario devuelve false. Ejemplos:

is_empty(IntList {})
  ⇒ true

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

int size(
  const IntList& a
)

Devuelve el tamaño (número de elementos) contenidos en la lista a. Ejemplo:

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

IntList cons_end(
  int value,
  const IntList& a
)

Devuelve una lista con los mismos elementos que la lista a pero con value al final. Ejemplo:

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

int sum(
  const IntList& a
)

Devuelve la suma de todos los elementos contenidos en la lista a. Devuelve 0 si la la lista está vacía. Ejemplo:

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

IntList duplicate(
  const IntList& a
)

Devuelve una lista con los mismos elementos que la lista a pero duplicados. Ejemplo:

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

int last(
  const IntList& a
)

Devuelve el último elemento de la lista a. Debes suponer que a tiene al menos un elemento. Ejemplo:

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

IntList but_last(
  const IntList& a
)

Devuelve una lista con los mismos elementos que la lista a excepto el último. Debes suponer que a tiene al menos un elemento. Ejemplo:

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

int maximum(
  const IntList& a
)

Devuelve el elemento más grande contenido en la lista a. Debes suponer que a tiene al menos un elemento. Ejemplo:

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

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

Devuelve una lista que es el resultado de concatenar la lista a con la lista b. Ejemplo:

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

IntList repeat(
  int n,
  int value
)

Devuelve una lista en la que value se repite n veces. Debes suponer que n es mayor o igual a cero. Ejemplo:

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

IntList reverse(
  const IntList& a
)

Devuelve una lista con los mismos elementos que la lista a pero en orden invertido. Ejemplo:

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

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

Esta función debe implementar el algoritmo de mezcla (merge). Devuelve una lista que es el resultado de intercalar, en orden ascendente, los elementos de las listas a y b. Debes suponer que a y b se encuentran ordenadas de manera ascendente. Ejemplo:

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
)

Devuelve true si la lista a es un prefijo de la lista b, o false en caso contrario. Una lista vacía es prefijo de cualquier otra lista. Ejemplos:

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
)

Devuelve una lista con los mismos elementos que la lista a pero insertando value en su lugar correspondiente. Debes suponer que a se encuentra ordenada de manera ascendente. Ejemplo:

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

IntList
  insertion_sort(
    const IntList& a
)

Devuelve una lista con los mismos elementos que la lista a pero ordendados de forma ascendente. La lista a se encuentra desordenada. Debes utilizar la función insert del problema anterior. Ejemplo:

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

IntList binary(
  int n
)

Devuelve una lista con unos y ceros que representa el valor en binario (sistema de numeración base 2) del número entero n. Por simplicidad, devuelve una lista vacía si n es igual a cero. Debes suponer que n es mayor o igual a cero. Ejemplo:

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