Recursión La recursión es un concepto amplio,
difícil de precisar. Aparece en numerosas actividades de
la vida diaria, por ejemplo, en una fotografía de una
fotografía. Otro caso muy ilustrativo de recursión
es el que se presenta en los programas de televisión en
los cuales un periodista transfiere el control a otro periodista
que se encuentra en otra ciudad, y éste hace lo propio con
un tercero. Aquí nos limitaremos a estudiar la
recursividad desde el punto de vista de programación. La
recursión permite definir un objeto (problemas,
estructuras de datos) en términos de sí mismo.
Casos típicos de estructuras de datos definidas de manera
recursiva son los árboles y las listas ligadas. Algunos
ejemplos de problemas que se definen recursivamente son el
factorial de un número, la serie de Fibonacci, etc.
Definición de recursividad Un subprograma que se llama a
sí mismo se dice que es recursivo. Ejemplo de Recursividad
Un ejemplo clásico donde se presenta la recursividad es en
la definición de un factorial: El factorial de N es la
multiplicación de N por el Factorial de N-1. Sea eso:
Factorial(N) = N * Factorial(N-1) Nótese que la
definición de la función se realiza en base a si
misma. Para que la ejecución de este código sea
posible, es necesario definir un caso base, en el caso del
factorial seria: Factorial(0) = 1. De este modo se tiene que:
Factorial(N) = IF(N==0) 1 ELSE N*Factorial(N-1)
Procedimientos recursivos Un procedimiento recursivo es
aquél que se llama a sí mismo. En el siguiente
procedimiento se utiliza la recursividad para calcular el
factorial de su argumento original. Java o C# Public static int
factorial(int n) { If (n <= 1) return 1; else return n *
factorial(n – 1); }
Consideraciones sobre procedimientos recursivos Condiciones de
limitación. Debe designar un procedimiento recursivo para
probar al menos una condición que pueda poner fin a la
recursividad; también debe supervisar los casos en los que
no se satisface ninguna condición dentro de un
número razonable de llamadas recursivas. Si no existe al
menos una condición que pueda cumplirse sin errores, el
procedimiento corre un riesgo elevado de ejecutarse en un bucle
infinito. Uso de la memoria. La aplicación tiene una
cantidad de espacio limitada para las variables locales. Cada vez
que un procedimiento se llama a sí mismo, utiliza
más cantidad de ese espacio para las copias adicionales de
sus variables locales. Si este proceso continúa
indefinidamente, se acaba produciendo un error Stack Overflow
Exception?.
Eficacia. Casi siempre se puede sustituir un bucle por la
recursividad. Un bucle no tiene la sobrecarga de transferir
argumentos, inicializar el almacenamiento adicional y devolver
valores. Su rendimiento puede ser mucho mayor sin llamadas
recursivas. Recursividad mutua. Si dos procedimientos se llaman
mutuamente, el rendimiento puede ser muy deficiente o incluso
puede producirse un bucle infinito. Este tipo de diseño
presenta los mismos problemas que un procedimiento recursivo
único, pero puede ser más difícil de
detectar y depurar. Llamadas con paréntesis. Cuando un
procedimiento se llama a sí mismo de manera recursiva,
debe agregar paréntesis detrás del nombre del
procedimiento, aun cuando no exista una lista de argumentos. De
lo contrario, se considerará que el nombre de la
función representa al valor devuelto por ésta.
Pruebas Si escribe un procedimiento recursivo, debe probarlo
minuciosamente para asegurarse de que siempre cumple ciertas
condiciones de limitación. También debería
comprobar que la memoria no resulta insuficiente debido a la gran
cantidad de llamadas recursivas.
MECANICA DE RECURSION. Es mucho mas difícil desarrollar
una solución recursiva para resolver un problema
especifico cuando no se tiene un algoritmo. No es solo el
programa sino las definiciones originales y los algoritmos los
que deben desarrollarse. En general, cuando encaramos la tarea de
escribir un programa para resolver un problema no hay
razón para buscar una solución recursiva. La
mayoría de los problemas pueden resolverse de una manera
directa usando métodos no recursivos. Sin embargo, otros
pueden resolverse de una manera mas lógica y elegante
mediante la recursión. Volviendo a examinar la
función factorial. El factor es, probablemente, un ejemplo
fundamental de un problema que no debe resolverse de manera
recursiva, dado que su solución iterativa es directa y
simple. Sin embargo, examinaremos los elementos que permiten dar
una solución recursiva. Antes que nada, puede reconocerse
un gran número de casos distintos que se deben resolver.
Es decir, quiere escribirse un programa para calcular 0!, 1!, 2!
Y así sucesivamente. Puede identificarse un caso
“trivial” para el cual la solución no
recursiva pueda obtenerse en forma directa. Es el caso de 0!, que
se define como 1. El siguiente paso es encontrar un método
para resolver un caso “complejo” en términos
de uno mas “simple”, lo cual permite la
reducción de un problema complejo a uno mas simple. La
transformación del caso complejo al simple
resultaría al final en el caso trivial. Esto
significaría que el caso complejo se define, en lo
fundamental, en términos del mas simple.
Examinaremos que significa lo anterior cuando se aplica la
función factorial. 4! Es un caso mas complejo que 3!. La
transformación que se aplica al numero a para obtener 3 es
sencillamente restar 1. Si restamos 1 de 4 de manera sucesiva
llegamos a 0, que es el caso trivial. Así, si se puede
definir 4! en términos de 3! y, en general, n! en
términos de (n – 1)!, se podrá calcular 4!
mediante la definición de n! en términos de (n
– 1)! al trabajar, primero hasta llegar a 0! y luego al
regresar a 4!. En el caso de la función factorial se tiene
una definición de ese tipo, dado que: n! = n * (n –
1)! Asi, 4! = 4 * 3! = 4 * 3 * 2! = 4 * 3 * 2 * 1! = 4 * 3 * 2 *
1 * 0! = 4 * 3 * 2] * ] = 24 Estos son los ingredientes
esenciales de una rutina recursiva: poder definir un caso
“complejo” en términos de uno más
“simple” y tener un caso “trivial” (no
recursivo) que pueda resolverse de manera directa. Al hacerlo,
puede desarrollarse una solución si se supone que se ha
resuelto el caso más simple. La versión C de la
función factorial supone que esta definido (n –1)! y
usa esa cantidad al calcular n!.
Con respecto al ejemplo de la función de Fibonacci, se
definieron dos casos triviales: fib(0) = 0 y fib(1) = 1. Un caso
complejo fib(n) se reduce entonces a dos más simples:
fib(n –1) y fib(n –2). Esto se debe a la
definición de fib(n) como fib(n –1) + fib(n –
2), donde se requiere de dos casos triviales definidos de manera
directa. Fib(1) no puede definirse como fib(0) + fib(-1) porque
la función de Fibonacci no está definida para
números negativos.
• Los parámetros y variables locales toman nuevos
valores en cada llamada (no se trabaja con los anteriores).
• Cada vez que se llama un método, el valor de los
parámetros y variables locales se almacenan en la pila de
ejecución. Cuando termina la ejecución se recuperan
los valores de la activación anterior. • El espacio
necesario para almacenar los valores en memoria (pila) crece en
función de las llamadas. • Con cada llamada recursiva
se crea una copia de todas las variables y constantes que
estén vigentes, y se guarda esa copia en la pila. •
Además se guarda una referencia a la siguiente
instrucción a ejecutar. • Al regresar se toma la
imagen guardada (registro de activación) en el tope de la
pila y se continúa operando. Esta acción se repite
hasta que la pila quede vacía. Consideraciones de la
recursividad