Recursividad

Implementación de Funciones Recursivas
(Ver capítulo 4 del Libro de Cairó y Guardati; pag. 109 – 128 y luego 129 ss)
La recursión es una potente característica del lenguaje C++ y otros lenguajes como
Pascal, Prolog y LISP, Java, herramientas de Visual Studio, etc. Básicamente consiste
en realizar la ejecución de una función sin que se haya terminado de realizar una o
más ejecuciones previas de lamisma.
Desde el punto de vista de quién hace la llamada a ejecución de la función recursiva,
hay dos tipos de recursión:
a) Directa, que es cuando dentro del cuerpo de una función se colocan llamadas
para que se invoque a sí misma. Vea la siguiente figura.

De la figura puede notar que la función volverá a iniciar una nueva ejecución,
quedando pendiente de finalizar la ejecución en curso. Lacantidad de llamadas
recursivas que se hagan dejará pendientes de concluir igual cantidad de invocaciones
previas.
b) Indirecta, que es cuando una función a llama a otra función b, que realiza
nuevas invocaciones a la función a. Vea la siguiente figura.

De la figura puede notar que la función FRecursiva2, que fue invocada por la función
FRecursiva1, vuelve a realizar una invocación a la primera. Lafunción FRecursiva1
inicia una nueva ejecución cuando aún está pendiente de finalización la ejecución
previa. En la figura se da el ejemplo de la recursión indirecta de dos funciones, pero
este tipo de recursión puede involucrar mayor cantidad de funciones.
Cada vez que se realice una llamada recursiva, se volverá a crear espacio para
contener las variables locales necesarias en la nueva llamada.Aunque tienen los
mismos nombres que las variables de las ejecuciones previas no concluidas, no se
crea ningún conflicto.
Muchos problemas se pueden resolver, y de hecho se definen, de manera recursiva.
Por ejemplo el factorial de un número n: por definición es n * (n – 1)!. De igual
forma, las personas concebimos muchas otras cosas de manera recursiva. A veces
se afirma que la recursividad es unaforma natural de solución de problemas. Por eso
se aconseja utilizarla para mejorar la legibilidad, comprensión del problema y para
facilitar la depuración del mismo. Por otro lado, al resolver problemas complejos por

métodos recursivos se puede escribe mucho menos código fuente, logrando
programas más compactos.
Pero la recursividad también tiene sus desventajas. Como ya se dijo anteriormentecada nueva invocación define un nuevo bloque de variables locales que consumirán
espacio de memoria. También crece la pila (stack) de direcciones de retorno de
subrutina. Estos dos aspectos pueden llevar al agotamiento de la memoria del
computador. Otra desventaja es el incremento en el tiempo de ejecución debido a la
pérdida de tiempo en la realización de la llamada, en la realización de nuevascopias
para variables locales y en el almacenamiento y recuperación de la dirección de
retorno de subrutina.
Cuando un programador utiliza recursión debe tener mucho cuidado en establecer
mecanismos de control. De lo contrario, una pérdida de control en una función
recursiva puede llevar a que el problema nunca se resuelva y al agotamiento de la
memora de la computadora, lo que llevaría a unaterminación fatal del programa.
Para evitar el problema de la pérdida de control en las llamadas recursivas ha de
implementarse dentro de la función una condición de terminación que sea efectiva,
es decir, que con seguridad se sepa que en algún momento será alcanzada. A esto,
algunos autores le llaman caso trivial, en lenguajes declarativos, o paso básico, en
lenguajes imperativos. Por el contrario, ala parte de la función que propicia la
recursividad le llaman caso general, en lenguajes declarativos, y paso recursivo, en
lenguajes imperativos. Siempre que se analice un problema de forma recursiva será
necesario determinar una o más circunstancias para ambas situaciones.
Desde el punto de la ubicación de la llamada recursiva dentro del cuerpo de la función
se conocen dos tipos:
a)

Recursión...