Recursividad: práctica 1

Para pensar la función recursiva, hay que determinar el caso base y el caso recursivo.

La pregunta para descubrir el caso base es:

Caso base: ¿cuál es el tamaño mínimo del problema (esto es, el tamaño mínimo del arreglo) para el cual se puede dar una solución inmediata?

Y la pregunta para descubrir el caso recursivo:

Caso recursivo: si la función ya supiera sumar arreglos de longitud \(N\) ¿qué debería hacer para sumar un arreglo de longitud \(N+1\)?

Las respuestas para el caso de la suma son:

• Caso base: se puede dar una solución inmediata si el arreglo es de tamaño 1, ya que: la suma de un arreglo con un solo elemento es, directamente, ese elemento:

  suma([7]) = 7
  suma([3]) = 3
  suma([0]) = 0
  suma([-1]) = -1
  

• Caso recursivo: si sumar un arreglo de, por ejemplo, tres elementos (\(N = 3\)) ya es un caso resuelto, se puede dar una solución a un arreglo de \(N + 1 = 4\) agregando al primer elemento la suma de los tres restantes:

  suma([7, 3, 9, 5])  =  7 + suma([3, 9, 5])
  

El código del caso base de la suma es trivial:

// Caso base solamente.
static int sumarRec(int arr[]) {
    if (arr.length == 1) {
        return arr[0];
    }
}

Para el caso recursivo se debe implementar el “achicamiento” del problema. En otras palabras, implementar:

// Pseudo-código del caso recursivo
if arreglo.length > 1:
    return arreglo[0] + sumarRec("mismo arreglo sin el primer elemento");

Por ejemplo:

// Pseudo-código con un arreglo de ejemplo
arreglo = [7, 3, 9, 5];
if arreglo.length > 1:
    return arreglo[0] + sumarRec([3, 9, 5]);

En Java, para pasar de [7, 3, 9, 5] a [3, 9, 5] es necesario realizar una copia del arreglo, pues no se pueden eliminar elementos.

Se podría implementar la siguiente función auxiliar:

// Devuelve una copia del arreglo sin su primer elemento.
static int[] borrarPrimero(int arreglo[]) {
    return null;
}

Con esta función, el pseudo-código quedaría tal que:

// Pseudo-código usando borrarPrimero().
arreglo = [7, 3, 9, 5];
if arreglo.length > 1:
    return arreglo[0] + sumarRec(borrarPrimero(arreglo));
                                 ^^^^^^^^^^^^^^^^^^^^^^

La complejidad de copiar un arreglo es \(\mathcal{O}(n)\) y no cambia aunque se descarte el primer elemento. El problema de realizar una copia en cada paso de la recursión es que la complejidad total de sumarRec se dispara a \(\mathcal{O}(n^2)\).

Para mantener la complejidad de la solución recursiva en \(\mathcal{O}(n)\) se debe evitar realizar copia alguna del arreglo.

El patrón recursivo para solucionar este problema es sustituir la copia del arreglo por un parámetro posición que indica cuál es la siguiente posición a sumar.

Un ejemplo sería:

// Pseudo-código para la recursión por índice:

sumarRec1([7, 3, 9, 5]) =

  arr[0] + sumarRec1("mismo arreglo, pero a partir del índice 1")
                                          ^^^^^^^^^^^^^^^^^^^^^

sumarRec1([7, 3, 9, 5], "a partir del índice 1") =

  arr[1] + sumarRec1("mismo arreglo a partir del índice 2")
                                    ^^^^^^^^^^^^^^^^^^^^^

sumarRec1([7, 3, 9, 5], "a partir del índice 2") =

  arr[2] + sumarRec1("mismo arreglo a partir del índice 3")
                                    ^^^^^^^^^^^^^^^^^^^^^

sumarRec1([7, 3, 9, 5], "a partir del índice 3") =

  → 3 es el úlimo índice, no hay llamada recursiva
    ^^^^^^^^^^^^^^^^^^^^

  return arr[3];

Ahora, por tanto, la función recursiva toma dos parámetros:

static int sumarRec1(int arr[], int pos);

• Caso base: si pos es el último índice válido, se devuelve directamente arr[pos].
• Caso recursivo: si no, se achica el problema incrementando en 1 el índice.

El código sería:

static int sumarRec1(int arr[], int pos) {
    // Caso base: pos es el último índice del arreglo.
    if (pos == arr.length - 1) {
        return arr[pos];
    }
    // Caso recursivo: incrementar índice en 1.
    return arr[pos] + sumarRec1(arr, pos + 1);
}

[Pendiente de explicar.]

[Pendiente de explicar.]