Recursividad

Definición

Un procedimiento o función se dice recursivo si
durante su ejecución se invoca directa o indirectamente a
sí mismo. Esta invocación depende al menos de una
condición que actúa como condición de corte
que provoca la finalización de la
recursión.

Un algoritmo recursivo consta de:

1- Al menos un caso trivial o base, es decir, que no
vuelva a invocarse y que se ejecuta cuando se cumple cierta
condición, y

2- el caso general que es el que vuelve a invocar al
algoritmo con un caso más pequeño del
mismo.

Los lenguajes como Pascal, que soportan recursividad,
dan al programador una herramienta poderosa para resolver ciertos
tipos de problemas reduciendo la complejidad u ocultando los
detalles del problema.

La recursión es un medio particularmente poderoso
en las definiciones matemáticas. Para apreciar mejor
cómo es una llamada recursiva, estudiemos la
descripción matemática de factorial de un
número entero no negativo:

Esta definición es recursiva ya que
expresamos la función factorial en términos de
sí misma.

Ejemplo: 4! = 4 * 3!

Por supuesto, no podemos hacer la
multiplicación aún, puesto que no sabemos el valor
de 3!

3! = 3 * 2!

2! = 2 * 1!

1! = 1 * 0!

0! = 1

Podemos ahora completar los
cálculos

1! = 1 * 1 = 1

2! = 2 * 1 = 2

3! = 3 * 2 = 6

4! = 4 * 6 = 24

Diseño de
Algoritmos Recursivos

Para que una función o procedimiento recursivo
funcione se debe cumplir que:

• Existe una salida no recursiva del procedimiento o
  función y funciona correctamente en ese
  caso.

• Cada llamada al procedimiento o función se
  refiere a un caso más pequeño del
  mismo.

• Funciona correctamente todo el procedimiento o
  función.

Para poder construir cualquier rutina recursiva teniendo
en cuenta lo anterior, podemos usar el siguiente
método:

• Primero, obtener una definición exacta del
  problema.

• A continuación, determinar el tamaño
  del problema completo a resolver. Así se
  determinarán los valores de los parámetros en
  la llamada inicial al procedimiento o
  función.

• Tercero, resolver el caso base en el que problema
  puede expresarse no recursivamente. Esto asegurará que
  se cumple el punto 1 del test anterior.

• Por último, resolver correctamente el caso
  general, en términos de un caso más
  pequeño del mismo problema (una llamada recursiva).
  Esto asegurará cumplir con los puntos 2 y 3 del
  test.

Cuando el problema tiene una definición formal,
posiblemente matemática, como el ejemplo del
cálculo del factorial, el algoritmo deriva directamente y
es fácilmente implementable en otros casos debemos
encontrar la solución más conveniente.

Ejemplo

Cálculo del factorial para enteros
no negativos

Cómo
funcionan los Algoritmos Recursivos

Para entender cómo funciona la recursividad es
necesario que tengamos presente las reglas y los tipos de pasaje
de parámetros provistos por Pascal.

Si un procedimiento o función p
invoca a otro q, durante la ejecución de
q se reservarán locaciones de memoria para
todas las variables locales de q y para los
parámetros pasados por valor. Al terminar la
ejecución de q este espacio es desocupado.
Ahora bien, si durante la ejecución de q
se produce una llamada a sí mismo, tendremos una segunda
"instancia" de q en ejecución, la primera
instancia se suspende hasta que la instancia recursiva termine.
Antes de iniciarse la ejecución recursiva de
q, se ocupan nuevas locaciones de memoria para
las variables locales y parámetros por valor de
q. Cualquier referencia a estas variables
accederá a estas locaciones. Las locaciones reservadas
durante la ejecución inicial de q son
inaccesibles para la 2da. instancia de
q.

Cuando la 2da. instancia de q termine,
el control vuelve a la primera instancia de q,
exactamente al lugar siguiente a la llamada recursiva. Cualquier
referencia a las variables locales o parámetros por valor
de q accederá a las locaciones reservadas
inicialmente, inaccesibles para la segunda instancia de
q.

Como vemos, no se conoce la cantidad de memoria que va a
utilizarse al ejecutar un procedimiento o función
recursivo sino que se produce una asignación
dinámica de memoria, es decir, a medida que se producen
instancias nuevas, se van "apilando" las que quedan pendientes:
se ponen al menos tres elementos en la pila:

• una para la dirección de vuelta,

• otra para el/los parámetro/s formal/es
  y

• otra para el identificador de la función que
  en esencia es un parámetro pasado por
  variable.

Cuando la última instancia de la recursión
– elige el caso base- se cumple, se "desapila" esa instancia y el
control vuelve a la instancia anterior; así hasta
"desapilar" todas las instancias.

Esta "pila" que se va generando en memoria es importante
tenerla en cuenta por lo que debemos asegurarnos que el algoritmo
recursivo no sea divergente.

Vamos a ver cómo funciona la recursión en
algunos problemas vistos a través de una traza
dónde iremos guardando los valores de los
parámetros formales.

Hagamos un recorrido del código de la
función factorial :

function factorial(n: integer):integer;

begin

if n=0 then factorial = 1 (* caso base *)

else factorial = n * factorial(n-1) (* caso general
*)

end;

La llamada inicial es: write(factorial(5)).

La primera instancia se coloca en la pila, luego a
medida que se va invocando la función, vamos apilando el
valor del parámetro formal que se envía:

Ejemplo

Dado un número natural N, encontrar
el dígito más significativo (el dígito
más a la derecha).

Diagrama de Llaves:

Cuándo
usar recursividad y cuándo
iteración

La potencia de la recursión reside en la
posibilidad de definir un número infinito de objetos
mediante un enunciado finito. De igual forma, un número
infinito de operaciones de cálculo puede describirse
mediante un programa recursivo finito, incluso si este programa
no contiene repeticiones explícitas. Los algoritmos
recursivos son apropiados principalmente cuando el problema a
resolver, o la función a calcular, o la estructura de
datos a procesar, están ya definidos
recursivamente.

Hay varios factores a considerar en la decisión
sobre si usar o no una solución recursiva en un problema.
La solución recursiva puede necesitar un considerable
gasto de memoria para las múltiples llamadas al
procedimiento o función, puesto que deben almacenarse las
direcciones de vueltas y copias de las variables locales y
temporales. Si un programa debe ejecutarse frecuentemente ( como
un compilador ) y/o debe ser muy eficiente, el uso de
programación recursiva puede no ser una buena
elección.

Sin embargo, para algunos problemas una solución
recursiva es más natural y sencilla de escribir para el
programador. Además la recursividad es una herramienta que
puede ayudar a reducir la complejidad de un programa ocultando
algunos detalles de la implementación. Conforme el costo
del tiempo y el espacio de memoria de las computadoras disminuye
y aumenta el costo del tiempo del programador, puede ser
útil usar soluciones recursivas en estos casos.

En general, si la solución no recursiva no es
mucho más larga que la versión recursiva, usar la
no recursiva. De acuerdo a esta regla, los ejemplos que hemos
visto no son buenos ejemplos de programación recursiva
aunque sirven para ilustrar cómo comprender y escribir
procedimientos y funciones recursivas, sería más
eficiente y sencillo escribirlas iterativamente.

La iteración y la recursividad cumplen con el
mismo objetivo: ejecutar un bloque de sentencias
n veces o que con una condición de fin
adecuada lo termine. Es importante distinguir las diferentes
instancias de la ejecución, los valores de las variables
determinan la instancia particular que está siendo
resuelta en ese momento. Es necesario que la ejecución del
bloque termine, es decir, el mismo bloque debe contener la
condición de corte que permita que cualquier instancia
menor del problema pueda ser resuelta directamente. Entonces,
cómo decir cuál alternativa es más
adecuada?. A veces la definición del problema no induce
ninguna estructura de control en particular, recién al
plantear un método de resolución es posible elegir
entre iteración y recursividad. Esta decisión tiene
que ver con la costumbre que tenga el programador al plantear sus
algoritmos y, una vez planteado un método de
resolución, se busca cuál herramienta conviene
más.

Hay problemas que aparecen más naturales para la
iteración y para otros para la recursividad, por ejemplo,
en problemas con contadores, sumatorias y productorias lo natural
es la iteración, pero en problemas en los que distinguimos
un caso base y uno general, como factorial, Fibonacci, MCD lo
natural es la recursión. Pero existe otro factor muy
importante a tener en cuenta: la eficiencia. Veamos el factorial
sin recursión:

Diagrama de Llaves:

La cantidad de iteraciones o de llamadas recursivas
respectivamente depende del tamaño de n,
el tiempo de ejecución de ambas no varía
sustancialmente, pero la versión iterativa reserva tres
lugares en memoria: para aux, prod y Fac, en cambio la
recursión guarda memoria para cada instancia y, si
n es grande, el espacio ocupado será mucho
más grande.

Hay problemas altamente complejos en lo que es casi
imposible aplicar iteración.

Ejemplo

Ejemplo

El Máximo Común Divisor entre
dos enteros A y B se define formalmente así:

Diagrama de Llaves

Ejemplo

Leer una cadena de caracteres terminada con un punto y
contar la cantidad de letras.

No se deben utilizar otras estructuras como string o
array.

Podemos expresarlo así: Contar la cantidad de
letras que siguen al caracter actual y luego si este caracter es
una letra incrementar el contador. Primero establezcamos una
definición formal del problema

Diagrama de Llaves

Notemos que en este procedimiento se pasa conta como
parámetro variable. Cómo queda la pila de
recursión?

Ejemplo

Imprimir los elementos de un vector en
orden inverso con un procedimiento recursivo.

Recomendamos realizar la traza de este procedimiento y
analizar qué sucedería si A fuera un
parámetro valor.

Ejemplo

Dado un arreglo A de enteros ordenado de forma
creciente, vamos a desarrollar el diagrama de llaves para la
función de Búsqueda Binaria que realiza la
búsqueda de un elemento clave en A de forma
recursiva.

Diagrama de Llaves

Problemas
Típicamente Recursivos

Se utilizan algoritmos recursivos generalmente
en:

– recorrido de árboles

– análisis de gramáticas y
lenguajes

– exploración y evaluación de expresiones
aritméticas

– juegos en los que un movimiento se puede dar en
función de otro de menor nivel o
complicación.

– métodos de ordenamiento más
eficientes

– Computación gráfica

Ejemplo

Torres de Hanoi

Se dan tres barras verticales y n discos de
diferentes tamaños. Los discos pueden apilarse en las
barras formando "torres". Los discos aparecen inicialmente en la
primer barra en orden decreciente y la tarea es mover los
n discos de la primer barra a la tercera de manera que
queden ordenados de la misma forma inicial. Las reglas a cumplir
son:

En cada paso se mueve exactamente un disco desde una
barra a otra.

En ningún momento pueden situarse un disco encima
de otro más pequeño.

Vamos a intentar resolverlo probando con 1
ó 2 discos:

1 disco

Mover el disco 1 de A a C

2 discos

Mover el disco 1 de A a B

Mover el disco 2 de A a C

Mover el disco 1 de B a C

Veamos qué pasa con 3 y 4
discos:

3 discos

Mover el disco 1 de A a C

Mover el disco 2 de A a B

Mover el disco 1 de C a B

Mover el disco 3 de A a C

Mover el disco 1 de B a A

Mover el disco 2 de B a C

Mover el disco 1 de A a C

4 discos

Podemos, partir de los movimientos para 3 discos,
resolver así: pasamos todos los discos de A a B menos el
disco base usando la barra C como auxiliar. Luego movemos la base
a C y volvemos a repetir los movimientos pasando los discos de la
barra B a C usando A como auxiliar

Mover el disco 1 de A a B

Mover el disco 2 de A a C

Mover el disco 1 de B a C

Mover el disco 3 de A a B

Mover el disco 1 de C a A

Mover el disco 2 de C a B

Mover el disco 1 de A a B

Mover el disco a de A a C (Movemos el disco
base)

Mover el disco 1 de B a C

Mover el disco 2 de B a A

Mover el disco 1 de C a A

Mover el disco 3 de B a C

Mover el disco 1 de A a B

Mover el disco 2 de A a C

Mover el disco 1 de B a C

Intentemos aplicar el mismo razonamiento para 8 discos.
Podríamos mover 7 discos de A a B, pasar el disco 8 a C y
luego mover los 7 discos de B a C. Para mover los 7 discos
aplicamos lo mismo: mover 6 discos de B a A, pasar el disco 7 de
C a B y luego mover los 6 discos de A a B. Podemos seguir
reduciendo el problema hasta llegar a 1 que es trivial, esto es,
el caso base es n=1 y el procedimiento Pascal recurisvo
sería:

Procedure Hanoi ( n: tipodiscos; Torre_A,
Torre_C, Torre_B: tipotorre);

begin

if n = 1 then MoverDiscoBase(Torre_A,
Torre_C)

else begin

Hanoi(n-1, Torre_A, Torre_B,
Torre_C);

MoverDiscoBase(n, Torre_A,
Torre_C);

Hanoi(n-1, Torre_B, Torre_C,
Torre_A)

end

end;

El procedimiento resultante es sencillo y pensar el
problema de manera iterativa no hubiese sido natural de acuerdo
al razonamiento efectuado además de la complejidad de
programación que originaría.

Autor:

Pablo Turmero