La recursión es una técnica de programación asociada a la solución de problemas matemáticos, los cuales se definen de manera recurrente. Es decir, en términos de problemas más pequeños. Si Pn es un problema de tamaño n y F es una función, representamos una función recursiva con la siguiente fórmula
Pn = F(Pn-1, Pn-2, Po) donde Pi es un Problema de tamaño i
Veamos un ejemplo.
Ejemplo 1: Factorial
Su definición matemática seria
N! = (N*(N-1)*(N-2)* … 1) para N>0
0! = 1
Si observamos el comportamiento de esta función:
1! = 1
2! = 2 * 1 = 2 * 1!
3! = 3*2*1 = 3 * 2!
…
N! = N*(N-1)!
Para cada N tenemos una formula recurrente: N! = N*(N-1)!
Si ahora queremos definir un algoritmo que acepta un entero N y retorna el valor del factorial de N (N!), podemos hacerlo de manera iterativa o recursiva.
Si intentamos programar esta función de manera iterativa, usando el lenguaje C, con las herramientas que disponemos hasta ahora, obtendríamos una función como la siguiente:
int Factorial (int A)
{
int prod = 1,i;
for (i = n; i=0; i–)
{
prod * = i ;
}
return (prod);
}
Este es un algoritmo ITERATIVO porque requiere la repetición explicita de cierto proceso (multiplicar por el anterior) hasta alcanzar determinada condición.
Si observamos la formula N! podemos notar que para cada N, esta depende del factorial calculado previamente, como habíamos notado anteriormente:
0! = 1
1! = 1*0!
2! = 2*1 = 2*1!
3! = 3*2*1 = 3*2!
4! = 4*3*2*1 = 4*3!
…
N! = N* (N-1)!
Podríamos reescribir la definición de la función matemáticamente como:
N! = N*(N-1)! para N > 0
N! = 1 para N = 0
Por lo cual la fórmula recurrente quedaría:
Factorial(N)= Factorial(N-1) * N para N > 0
Factorial(0)= 1 para N = 0
En esta fórmula observamos que Factorial está definida en términos de si misma, pero en un problema más pequeño. Escribiendo el algoritmo recursivo en lenguaje C, basándonos en la fórmula recurrente:
int factorial(int n)
{
if (n == 0)
return(1);
else
return(n * factorial(n-1));
}
Note que la función se llama a si misma, a esto se le conoce como invocación recursiva. Este es el ingrediente principal de una función recursiva. Se supone que la función calculada ya ha sido escrita y se usa en la propia definición. Es importante puntualizar que la invocación recursiva debe hacerse con cuidado porque puede producirse un ciclo infinito de llamadas. Por lo tanto, en toda función recursiva debe existir una condición de parada. En el ejemplo, la condición de parada se alcanza en n=0.
¿Cómo sería la ejecución de una función recursiva?
¿Afecta el pasaje de parámetros?
Para ilustrar esto efectuaremos la corrida de la función factorial para n=4, de forma recursiva. Llevaremos acabo este pequeño ejemplo paso por paso, para así llegar a entender de manera clara la forma en que se ejecutará una función recursiva.
Sabemos de antemano que factorial(4) debe dar como resultado 12.
Veamos lo que ocurre en la pila de invocación que se muestra en la siguiente tabla:
Para cada nueva llamada de factorial. Se crea un nuevo registro de activación dentro de la pila de invocación donde el parámetro N cambia al valor indicado en la invocación. A si van a existir varias generaciones de parámetros simultáneamente, una en cada registro. Sólo se hace referencia a la copia mas reciente, es decir, a la copia de la generación actual.
Note que en este caso usamos más memoria que el algoritmo iterativo. Lo cual, para este ejemplo, nos dice que es mejor el iterativo en cuanto a recursos. En cuanto a legibilidad, ambos son buenos.
Ejemplo 2 : Números de Fibonacci
La serie de Fibonacci está formada por los números 0,1,1,2,3,5,8,13,21,34……………
Esta serie se construye obteniendo cada elemento como la suma de los anteriores. Es decir,
0,1,0+1,1+1,1+2,2+3,3+5,5+8,8+13,13+21,…
Debemos tomar dos números iniciales, que corresponden a las dos primeras posiciones de la seria.
Asi, suponemos que
Fib (0) = 0
Fib (1) = 1
Fib (2) = Fib (1) + Fib (0)
Fib (3) = Fib (2) + Fib (1)
…
Fib (n) = Fib (n-2) + Fib (n-1) n ( 2
Por lo que la definición matemática sería:
Note que esta definición hace referencia a si misma dos veces. En este caso decimos que tenemos recursión tipo árbol. Cuando hay una sola llamada recursiva se dice que la recursión es por la cola.
La implementación de la definición recursiva de los números de fibonacci en lenguaje C quedaría:
int Fib (int n)
{
if ( n <= 1 )
{
return(n);
}
else
return(Fib(n-2) + Fib(n-1));
}
En esta implementación, los casos bases de la recursión fib(0)=0 y fib(1)=1 son cubiertos por la condición de parada n = 1.
La corrida de esta función es mucho más complicada porque tenemos dos invocaciones recursivas que deben resolverse en el segundo return. Veamos que ocurre para n=4, donde el resultado debe ser 3:
El árbol de invocación para Fib (4) sería:
Note que hay muchas llamadas redundantes, seria mucho más eficiente recordar el valor. Se podría hacer el algoritmo iterativo pero es antinatural, ya que la definición de la función es naturalmente recursiva. Escriba un algoritmo iterativo como ejercicio.
En este caso en cuanto a recursos es mucho mejor el iterativo, pero en cuanto a legibilidad es mejor el recursivo.
Hasta aquí parece que la recursión es algo formal que no me ayuda en la computación de muchas actividades. Veamos un ejemplo donde la recursión mejora significativamente el tiempo de corrida de un algoritmo.
Ejemplo 3: Búsqueda Binaria
Consideremos un arreglo de elementos donde los objetos se colocan en orden ascendente.
-25 | -17 | -13 | -9 | -7 | -3 | 0 | 4 | 10 | 26 | 39 | 45 | 49 | 54 | 63 | 70 |
Algunos ejemplos de la vida real con elementos ordenados son: un diccionario, un directorio telefónico, una lista de estudiantes, una lista de carros robados ordenados por placa, etc.
Queremos encontrar un elemento dentro del arreglo. En la vida real, una palabra en el diccionario, la dirección de una persona, la nota de un estudiantes, un carro robado.
La búsqueda es una actividad muy común en computación. Debería ser eficiente. Nosotros conocemos el algoritmo de búsqueda secuencial o lineal, es decir, buscar desde el primer elemento hasta encontrarlo. Este algoritmo es aplicable cuando los elementos están en desorden. En el caso de elemento ordenado, no tiene sentido aplicar este algoritmo. Naturalmente al buscar en un diccionario, no se busca desde el principio sino que se intenta buscar en una de las dos mitades, y asi sucesivamente hasta encontrar la palabra. Al algoritmo que se uso de manera natural al buscar en un diccionario se le conoce como algoritmo de búsqueda binaria y es el que explicaremos a continuación.
Veamos la representación gráfica del proceso. Se pregunta por el elemento del medio (a), si este no es el buscado ahora se toma la mitad donde se encuentra el elemento. Es decir, preguntamos si el elemento es menor que a, en cuyo caso buscamos en la primera mitad. Nuevamente se obtiene el elemento del medio (b), en el sub arreglo considerado. Y asi sucesimente se aplica el algoritmo hasta encontrar el elemento buscado o llegar a una casilla donde podemos decidir que el elemento no se encuentra.
Observe que la búsqueda binaria es un método recursivo. Pues se aplica el mismo proceso sobre el nuevo sub-arrego. Para determinar el sub-arreglo debemos saber cuáles son los límites inferior (linf) y superior (lsup) dentro del arreglo original, es decir, el índice donde comienza el sub-arreglo y el índice donde finaliza el mismo. Veamos el algoritmo:
En este caso los cálculos no serian redundantes pues la recursión solo recorre una rama del árbol.
Ejercicio: Realice la corrida para el arreglo dado como ejemplo y los valores de x=10 y x=15, observe lo que ocurre.
Características de la Recursión
La Recursión posee ciertas características que deben cumplirse para que la misma llegue a desarrollarse adecuadamente de lo contrario podría generar gran cantidad de problemas en el programa.
Debe tener una condición de parada.
Es un buen estilo de programación colocar la(s) invocación(es) recursiva(s) al final de la función.
En general es menos eficiente en tiempo y espacio, asi que debe considerar esto a lo hora de elegir un algoritmo recursivo.
En ocasiones es la solución más natural y lógica a un problema.
Compromiso entre la eficiencia de la máquina y la eficiencia del programador (costo del programa aumenta mas rápido que costo de computación).
Ejemplo 4: Torres de Hanoi
Figura 3.1 . Torres de Hanoi
El problema consiste en mover N discos de un eje (A) a otro (C), cumpliendo ciertas reglas:
Un disco de tamaño mayor no se puede colocar sobre un disco más pequeño.
Sólo se puede mover un disco a la vez.
"Pasar los 4 discos desde el eje A hasta el eje C usando B como auxiliar" es el problema que queremos resolver representado en la figura.
Al tratar de definirlo en términos de un problema más pequeño, la definición recursiva quedaría
Mover la torre de Hanoi de N-1 disco desde el eje A hasta el eje B
"Mover el disco N (más grande) desde el eje A hasta el eje C"
Mover la torre de Hanoi de N-1 disco desde el eje B hasta el eje C
La solución trivial (caso base) es con N = 1.
"Mover el disco 1desde el eje A hasta el eje C."
Note que la instrucción "Mover la torre de Hanoi de N-1 disco desde el eje A hasta el eje B" sería una invocación recursiva
Figura 3.2. Ejercicio torres de Hanoi
Autor:
Pablo Turmero