La recursión

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.

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