Recursividad

Palabras clave: Recursividad, Inducción, Backtracking.

Preguntas de repaso

¿Cómo se realiza una búsqueda binaria?
¿Cómo se hace una ordenación por inserción?

No sigas si no conoces las respuestas.

1. Definición recurrente

Los términos recurrente (castellano), recursivo y recursión (informáticos) se consideran "equivalentes" para el concepto de ``definirse en función de sí mismo''. Un objeto es recursivo si queda definido mediante un proceso basado en su propia definición.

Ejemplo 1. Los axiomas de Peano

Se muestran los primeros axiomas de Peano que permiten construir recursivamente el conjunto de los números naturales.

Ax 1.: El 0 es un número natural.
Ax 2.: Si n es un número natural, entonces s(n) es un número natural. Donde s(n) se lee ``el siguiente de `n’'.
Ax 3.: Para cada n, el siguiente no es el 0: s(n) != 0.
Ax 4.: Si s(n)=s(m) entonces n=m.

Estos 4 axiomas definen un proceso por el que se determina que es un número natural y qué no lo es. Es una definición recursiva pues se dice que "algo es natural si algo que depende de él es natural" (ver el Ax. 2)

Una definición recurrente es aquella que se utiliza en su definición. Es correcto decir que uno es humano si su ascendiente es humano, pero a poco que apliquemos varias veces la definición y de acuerdo a las reglas evolutivas terminamos en la familia previa a los homínidos y podemos concluir en los primeros mamíferos. Para establecer una definición recurrente se requieren de ciertas normas para garantizar que el ciclo finalice en algún momento. Toda definición recursiva establece un proceso que debe venir dado por 3 reglas.

Regla Base: es la que indica cuáles son los ejemplos o casos particulares que cumplen la definición. Es imprescindible para hacer una definición recursiva.
Regla Recursiva: realmente es un conjunto de reglas que aplicándolas establece cuándo un objeto responde a la definición, reglas en las que deben de aparecer de nuevo el concepto a definir. Es una parte imprescindible. También recibe el nombre de pasos recursivos.
Regla de Exclusión: es un conjunto de reglas que indica cuándo un objeto no se ajusta al concepto en términos de la regla base y la regla recursiva. Normalmente esta parte va implícita y es opcional.

Ejemplo 2. Los axiomas de Peano como definición recursiva

Los dos axiomas de Peano indicados anteriormente responden a una definición recurrente. En concreto:

Regla Base: Se corresponde con el Ax. 1, pues indica un ejemplo (o caso particular) al que se le asocia la definición. No se platea por qué, solo se dice que ese objeto, el 0, responde al concepto.
Regla Recursiva: Se corresponde con el Ax. 2, pues indica cómo se sabe si otro número responde a un natural. Se sabe si dicho número es natural si es el siguiente, del siguiente, del siguiente, …. del siguiente de un objeto del caso base (en este caso del cero).
Regla de Exclusión: Establecen las condiciones de que el ejemplo inicial considerado, llamado ``cero'', no puede ser el siguiente de otro número (para evitar también el ciclo sin fin), y que un número no se puede ser el siguiente de dos números diferentes obtenidos previamente.

2. Recursividad Estructural

Toda definición recursiva tiene asociado un proceso de "construcción de objetos", que es lo que formalmente se conoce como Recursividad Estructural. En una definición estructural se establece cómo un nuevo objeto x, que responde a una definición recursiva, se construye a partir de una serie de objetos {y1, y2,…, yn}, que responden a la misma definición y se definen antes que el elemento x.

Ejemplo 3. Ejemplos de recursividad estructural

En el ejemplo de los números naturales, dado un número natural n se puede construir un nuevo número natural, m, realizando la operación n+1. En este caso, el objeto construido m se construye a partir de un objeto previo que es n realizando una operación aditiva.

Otros ejemplos son:

Un producto es el resultado de multiplicar un producto (previo) por un número.
Una suma es el resultado de sumar una suma (previa) más un número.
La solución a un puzzle es el resultado de añadir adecuadamente a una solución (previa, más pequeña) del puzzle una pieza del puzzle.
Construir una pared es el resultado de añadir correctamente a un pared (previa, más pequeña) un nuevo ladrillo.

En general, la regla de una recursividad estructural es:

La solución de un problema de tamaño n se obtiene a partir de la solución del problema para un tamaño menor (normalmente para tamaño n-1) a la que se "añade" de forma adecuada un nuevo elemento. Dicho elemento, si fuese el caso, puede ser la solución del problema para un tamaño menor a n.

3. Función recursiva

La programación como técnica para la resolución de problemas también contempla la recursividad. Una primera definición al concepto de recursividad desde la perspectiva de la programación es:

Una función es recursiva si en su cuerpo se invoca a sí misma.

Indicar que solo se puede construir una función recursiva si sus acciones responden a una recursividad estructural; es decir, que existe una definición recursiva que las justifica. Por tanto, toda función recursiva deberá contemplar una regla base, una regla recursiva y, si fuese necesario, una regla de exclusión.

Ejemplo 4. Un ejemplo de función recursiva

La siguiente función es una función recursiva. Observa dónde se indican los casos base y recursivo.

1
2
3
4
5
6 int sum (int limite) {
    if (limite == 1)  // Caso base
        return 1;
    else
        return limite + sum (limite - 1); // Caso recursivo
}

Mención especial sobre los dos casos: * El caso base es aquel en el que la función no se llama a sí misma y, por tanto, establece la condición de terminación. Es imprescindible para que la función deje de ejecutarse. * El caso recursivo responde a una recursividad estructural. En efecto, la solución del problema es limite + sum (limite - 1), que está formada por la solución del problema para un caso anterior sum (limite - 1) a la que se le "añade" un elemento, el valor limite.

Ejecuta la función anterior para la invocación sum(0). ¿Qué está pasando?

Se debe a que no se ha puesto el caso excluyente: ¡impleméntalo!.

Un esquema general que puedes considerar para cualquier función recursiva es

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13 tipo_dato  funcionRecursiva  (parametros) {
  if (parametros no posibles) return error;  //  Regla de exclusión.

  if (parámetros son caso base)  { // Regla base.
  	Calcular solución inmediata.
  	return solución
  }
  else {  // Regla recursiva.
     solución parcial =  funcionRecursiva ( parametros para problema más pequeño )
     Calcular solución a partir de la solución parcial.
     return solución
  }
}

Después, modifica dicho esquema adecuadamente en función de tus necesidades.

4. Backtracking

Hay muchos problemas catalogados como "problemas combinatorios", donde la solución buscada se corresponde con una combinación de elementos. Por ejemplo el problema de colocar 8 reinas en un tablero de ajedrez sin que se ataquen es uno de tales problemas. El sudoku es otro problema combinatorio.

El problema se complica cuando es un "problema de optimización combinatoria", donde el objetivo consiste en encontrar la mejor solución (o combinación) posible existente. Un ejemplo es el problema de la mochila, que consiste en llenar una mochila (léase coche o camión) con la combinación de objetos que maximicen el valor económico de lo transportado y, claro está, sin que exceda el peso máximo que pueda ser trasladado.

El algoritmo básico que resuelve este tipo de problemas es el algoritmo de Backtracking. Los problemas que se pueden resolver con backtracking son aquellos que cumplen estas dos condiciones:

La solución se puede expresar como una n-tupla, \((x_1,x_2,\ldots,x_n)\), donde cada \(x_i\) se selecciona de entre un conjunto finito de valores \(S_i\).
El problema se puede formular como buscar aquella tupla que cumpla ciertas restricciones.

Dichas restricciones puede ser que optimice (maximice o minimice) un determinado criterio \(P(x_1,x_2,\ldots,x_n)\).

El algoritmo básico para aplicar backtracking es un algoritmo recursivo que se basa en ser sistemático y exhaustivo: ir generando todas las posibles soluciones candidatas, de acuerdo a algún "sistema" establecido, hasta llegar a una solución final.

Una solución candidata se va construyendo poco a poco, siguiendo el siguiente "sistema":

La idea general es que primero se seleccione un valor del primer elemento de la tupla, \((x_1)\), después un valor para el segundo elemento de la tupla, \((x_1,x_2)\), y así sucesivamente se van añadiendo elementos al vector mientras que se cumplan las condiciones \(P()\).
- Cada una de esa tuplas recibe el nombre de tupla candidata.
- Si la tupla candidata tiene un elemento se dice que es de tamaño 1, si tiene dos elementos se dice que es de tamaño 2, y así sucesivamente.
Cuando se tiene una tupla candidata de tamaño \(k-1\), como \((x_1,x_2,\ldots,x_{k-1})\), la idea general nos dice que hay que añadir un nuevo elemento \(x_k\) para poder llegar a la solución final. Cuando añadimos un elemento \(x_k\) se dice que se alcanza la primera solución candidata de tamaño \(k\) a partir de la tupla candidata \((x_1,x_2,\ldots,x_{k-1})\), y que es la tupla \((x_1,x_2,\ldots,x_{k-1}, x_k)\).
Como las tuplas candidatas deben cumplir ciertas condiciones \(P()\), cada vez que se quiera añadir un nuevo elemento se tendrá que comprobar si cumple con los criterios que permitan añadir o no un nuevo elementos al vector. En concreto, imagina que creas tu primera solución candidata de tamaño \(k\): \((x_1,x_2,\ldots,x_{k-1}, x_k)\). El hecho de haberla creado no significa que cumpla las condiciones (por algo se llama candidata). Pueden ocurrir dos cosas:
- que la solución candidata cumpla con las condiciones, con lo cual se podrá añadir un nuevo elemento \(x_{k+1}\) y por tanto se podrá seguir con el esquema de la idea general; o por el contrario
- que la primera solución candidata no cumpla con las condiciones, lo que quiere decir que en algo estamos fallando en la búsqueda de la solución. Ese "fallo" puede deberse a dos motivos:
  1. Hemos hecho mal al considerar que el elemento \(x_k\) puede llevarnos a la solución.
    
    En este caso probamos con otro valor \(x'_k\) construyendo una segunda solución candidata: stem[(x_1,x_2,\ldots,x_{k-1}, x'_{k})] y repetimos el proceso.
    
    Si a pesar de probar con una segunda solución se siguen violando las restricciones \(P()\) entonces probamos con una tercera, una cuarta, … solución candidata, todas ellas de tamaño \(k\).
    
    Si alguna de ellas cumple las condiciones, entonces "saltará" la condición previa y se añadirá un nuevo elemento \(x_{k+1}\) pero si hemos probado todas las soluciones candidatas de tamaño \(k\) y todas ellas violan las restricciones, entonces es que se está dando otro motivo y que es el siguiente:
  2. Hemos hecho mal al considerar que el elemento anterior \(x_{k-1}\) puede llevarnos a la solución. Entonces tendremos que volver atrás, a la solución candidata \((x_1,x_2,\ldots,x_{k-1})\), para probar con otro valor candidato \(x'_{k-1}\) y volver a repetir todo el proceso. En el peor de los casos puede que no haya valor alguno para la posición \(k-1\) que permita llegar a una solución, entonces tendremos que volver atrás para la solución candidata \((x_1,x_2,\ldots,x_{k-2})\)

Toda solución candidata:

o se "extiende" agregando un elemento más en el vector solución,
o se "descarta" ya sea estudiando un nuevo valor del último elemento añadido o volviendo atrás para volver a una solución candidata de menor tamaño y analizar otro caso.

Si en aplicación de la idea general se llega a una solución candidata de tamaño \(n\) que cumpla las restricciones entonces tendremos una solución; pero si siempre volvemos atrás y no conseguimos llegar nunca a un vector de tamaño \(n\) entonces el problema no tiene solución. Es más, no se tiene solución si el vector resultante es un vector sin elementos (observa que cada vuelta atrás lo que hace es reducir en una unidad la longitud del vector).

Al final de este tema tienes un ejemplo completo en el que se muestra la idea de los algoritmos backtracking en la búsqueda de caminos en un mapa.

Un posible pseudocódigo del algoritmo es el siguiente:

backtracking (solParcial, k) {
    if rechazar(solParcial, k) then return; // Caso excluyente

    if esSolucion(solParcial, k) then  // Caso base
        procesarSolucion(solParcial, k)  // P.e. un return/print de la solución
        exito = true;
        return solParcial // Retorna la solución parcial como solución del problema.

    for (x_k en S_k) {
        solParcial[k] = x_k;
        sol = backtracking (solParcial, k+1) // Caso recursivo
        if (exito) then return sol;
    }

    if (terminado) then return;
}

donde

backtracking (solParcial, k) debe leerse como la aplicación de la función backtracking en la k-ésima etapa (o paso) para la solución parcial solParcial obtenida en las k-1 etapas (pasos) anteriores.
solParcial representa una solución parcial, inicialmente vacía. La función será invocada inicialmente con k=0.
rechazar(solParcial, k) es una función que comprueba si se cumplen las restricciones impuestas sobre la solución candidata. Si no se cumplen se rechaza y se vuelve atrás. Estas restricciones son diferentes a las de comprobar si es solución o no.
solucion (solParcial, k) es una función que comprueba si con los k-elementos que componen la solución parcial se consigue una solución correcta. Si es así, entonces se invoca a
procesarSolucion(solParcial, k) que hará lo que corresponda para procesar la solución y parar el proceso.
Si nos encontramos con un solución candidata que cumple las restricciones y no es solución, entonces tendremos que añadir un nuevo elemento al vector recorriendo todos sus posibles valores, como se indica en el for().
- En primer lugar tratamos de extenderla con un elemento más. Lo que en el algoritmo aparece como una simple asignación a un vector se deberá de adaptar al problema para que se incorpore un nuevo elemento en la solución.
- Para la nueva solución candidata volvemos a repetir el proceso con la invocación backtracking (solParcial, k+1).
- La condición de terminado es un condicional que suspende la búsqueda. Suele venir dado por la función procesarSolucion().
- La condición terminado indica que ya no quedan más posibles extensiones de la solución parcial.

Hay más formas de expresar el algoritmo. No te ciñas solo a un modo de proceder. Por ejemplo, también se puede implementar según este otro esquema.

backtracking (solParcial, k)
    if estadoImposible(solParcial, k) return null

    do {
        Tomar el siguiente x_k en S_k
        if (valido(solParcial, k)) {
            if (esSolucion(solParcial, k) {
                solParcial[k] = x_k;
                return solParcial;
            }

            solParcial[k] = x_k;
            sol = backtracking (solParcial, k+1) // Caso recursivo
            if (sol != null) then return sol;
        }

    } while (queden elementos s_k en S_k);

    return null;

El esquema anterior establece que al añadir un elemento a la solución parcial pueden ocurrir dos cosas. Que la solución parcial sea válida o que no lo sea. Si no lo es se debe de probar con el siguiente elemento. Pero si es válida puede ocurrir dos cosas, que sea una solución final - caso base, en cuyo caso retornamos la solución - o que aún debemos seguir buscando por un camino prometedor - caso recursivo, en cuyo caso retornamos lo que diga la recursividad. La primera línea comprueba si los parámetros son acordes a lo esperado.

La diferencia entre ambos algoritmos, que en esencia son el mismo, se encuentra en que mientras que el primero se invoca recursivamente sin saber si se va por buen camino, en el segundo la llamada recursiva solo se realizará si la solución parcial es válida. Utilizar un esquema u otro depende del problema y de la concepción que tengamos en la resolución del mismo. En cualquier caso no son esquemas únicos y los tendrás que adaptar a tus circunstancias particulares.

5. Árbol de llamadas

Un árbol de llamadas (o de recursión) representa gráficamente las sucesivas llamadas recursivas que un programa recursivo puede generar. El nodo superior (nodo raíz) representa a la primera invocación que se hace a la función y todas las invocaciones recursivas aparecen debajo de él en el orden en el que se realicen las llamadas. El nodo más inferior (nodo hoja) representa a la última invocación que se corresponde con un caso base. Los nodos se etiquetan con el nombre de la función y sus argumentos. Por simplicidad, en algunos casos que no generen confusión, se puede obviar el nombre de la función y etiquetar los nodos solo con los argumentos.

Como ejemplo considera la función factorial(n), que calcula el producto de los primeros n-números naturales. Se puede expresar de forma recursiva mediante el siguiente programa:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10 int factorial (int n) {
  if (n<1) return -1;  //  Regla de exclusión.

  if (n==1)  { // Regla base.
  	return 1;
  }
  else {  // Regla recursiva.
     return n * factorial(n-1);
  }
}

Cuando realizamos la invocación factorial(3), se aplicará la regla recursiva para factorial(2). Para factorial(2), se aplicará la regla recursiva invocando a factorial(1) que aplicará el caso base.

Asociado a todo árbol de llamadas podemos construir el árbol de reconstrucción de soluciones. Tiene la misma estructura que el árbol de llamadas pero los arcos tiene el sentido contrario.

Podemos representar simultáneamente ambos árboles de la siguiente forma:

Se define la serie de Fibonacci como la secuencia: 1, 1, 2, 3, 5, … donde cada término se obtiene a partir de la suma de los dos términos inmediatamente anteriores; salvo los dos primeros términos que vienen dados. Se pide:

Construye un función que calcule la serie de Fibonacci para los primeros 5 términos.
Dibuja el árbol de llamadas.
Completa el árbol con el de sus soluciones.

6. Repaso

Una definción recursiva es aquella donde lo definido está en la definición.
Toda definición recursiva consta de 3 reglas: la R. base, la R. recursiva y la R. de exclusión.
Toda definición recursiva tiene asociado un procedimiento (de recursividad estructural) que construye los objetos definidos.
En términos informáticos las definiciones/precedimientos recursivos se traducen en funciones que se invocan a sí mismas, y se llaman funciones recursivas.
Las invocaciones recursivas se representan mediante el árbol de llamadas.

7. ANEXO. Un ejemplo de bactracking

Imaginemos que el siguiente dibujo representa el esquema de una mapa de carreteras que une dos ciudades S y T pasando por los puntos P1 y P2 que son de difícil acceso.

Una representación de este tipo recibe el nombre de grafo. En un grafo están los nodos (los círculos) y los arcos (las flechas). En nuestro caso los nodos representan puntos de paso y los arcos representan la existencia de caminos. Los números que aparecen en los arcos representan la distancia que hay entre los puntos (en kilómetros). Además, el grafo nos indica que hay caminos distintos para ir entre P1 y P2, siendo el trayecto de P1 a P2 más largo que el de P2 a P1.

Si nos pidieran que buscásemos cuál es el trayecto con una longitud de no más de 8Km y que pase por todos los puntos, partiendo de S y finalizando en T, entonces nuestra solución será un vector de longitud 4 de la forma {S, P, P', T} donde S representa a la ciudad S, T representa a la ciudad T y P y P' toma valores en el conjunto de puntos {P1, P2}. Para encontrar una solución podemos proceder como sigue:

Empezamos con un solución candidata {S}. La longitud de este camino es de 0Km y como cumple las condiciones entonces añadimos un punto más.
Consideramos como primera solución candidata de longitud 2 a {S, P1}.

La longitud de este camino es de 3Km, y como es menor que 8Km añadimos un nuevo elemento.
Consideramos como primera solución candidata de longitud 3 a {S, P1, P1}. El grafo asociado a esta solución parcial es el mismo del paso anterior. La longitud de este camino es de 3Km así que añadimos el 4 elemento.
Como el único valor posible para la cuarta posición es la T, la solución candidata es {S, P1, P1, T}, y tiene asociado el siguiente trayecto.

Ya que la solución no contiene a todos los puntos del mapa, viola las restricciones impuestas a la solución, por lo que estamos forzados a volver atrás (pues en la posición 4, el único valor posible es T).
Probamos un nuevo valor para la solución candidata de longitud 3, y consideramos ahora {S, P1, P2}.

La longitud de este camino es de 6Km, que es menor de 8Km, así que añadimos el 4 elemento.
Obtenemos entonces la solución {S, P1, P2, T}.

Esta vez sí contiene a los 4 puntos, pero la longitud del trayecto es de 10km, que supera los 8Km. Por lo que volvemos de nuevo atrás.
Al volver a la solución candidata de longitud 3, {S, P1, P2}, observamos que no tenemos más valores posibles para la tercera posición (ya hemos probado todos sus valores posibles) así que lo que está fallando es el valor asignado a la posición anterior. Así pues, volvemos a hacer una vuelta atrás.
Estamos ahora en la primera solución parcial de tamaño dos {S, P1}, y que por los pasos anteriores no nos lleva a ninguna solución. Así que generamos la segunda solución parcial de tamaño dos: {S, P2}.

Como es de longitud inferior a 8Km, añadimos un nuevo elemento al vector.
Probamos ahora como primera solución candidata de longitud 3: {S, P2, P1}

Que al ser de longitud inferior a 8Km, podemos añadir un cuarto elemento a la solución candidata:
Al añadir el cuarto elemento la solución candidata es {S, P2, P1, T}

Es una solución que contiene a todos los puntos del mapa y tiene una longitud inferior a 8 Km. Así que ya tenemos una solución al problema con lo que finalizamos el proceso de búsqueda.

Notar que si nos hubiesen pedido obtener una solución para un camino con una longitud inferior a 6Km, entonces el vector final sería le vector vacío.

Observa que si te hubiesen pedido obtener el trayecto más corto que pase por n-puntos entonces el algoritmo sería otro - aunque se base en backtracking - y que se puede expresar en los siguientes pasos:

Obtener una solución que conecte los n-puntos (no importa lo que mida). Llamemos MAX al valor del trayecto.
Volver a aplicar el algoritmo de backtracking imponiendo la búsqueda de un trayecto con una longitud estrictamente inferior a MAX.
Si se obtiene un nuevo camino con longitud LONG cumpliendo que LONG<MAX, entonces hacer la asignación MAX=LOG y volvemos al paso 2.
Pero si no se obtiene ningún nuevo camino con una longitud menor que MAX, entonces la solución es el último camino que determinó el valor de MAX.

Este algoritmo se conoce como algoritmo BRANCH AND BOUND (ramificación y poda).