5.4 Recursividad

Un objeto es recursivo si forma parte de sí mismo o interviene en su propia definición. El instrumento necesario para expresar los programas recursivamente es el subprograma. La mayoría de los lenguajes de programación admiten que un procedimiento o función haga referencia a sí mismo dentro de su definición, esto se denomina recursividad directa.

La recursión se puede considerar como una alternativa a la iteración y resulta muy útil cuando se trabaja con problemas o estructuras, como los árboles, definidos en modo recursivo (aunque las soluciones iterativas son más cercanas a la estructura de un computador).

Para comprender la recursividad se deben tener en cuenta las premisas:

  • Un método recursivo debe establecer la condición o condiciones de salida.
  • Cada llamada recursiva debe aproximar hacia el cumplimiento de la/las condiciones de salida.
  • Cuando se llama a un procedimiento o función los parámetros y las variables locales toman nuevos valores, y el procedimiento o función trabaja con estos nuevos valores y no con los de anteriores llamadas.
  • Cada vez que se llama a un procedimiento o función los parámetros de entrada y variables locales son almacenados en las siguientes posiciones libres de memoria y cuando termina la ejecución del procedimiento o función son accedidos en orden inverso a como se introdujeron.
  • El espacio requerido para almacenar los valores crece conforme a los niveles de anidamiento de las llamadas.
  • La recursividad puede ser directa e indirecta. La recursividad indirecta se produce cuando un procedimiento o función hace referencia a otro el cual contiene, a su vez, una referencia directa o indirecta al primero.

Todo algoritmo recursivo puede ser convertido en uno iterativo equivalente, aunque para ello se puede requerir la utilización de ciertas estructuras de datos (pilas) para realizar el almacenamiento de ciertos datos.

Ejercicio: Mediante un diagrama de flujo diseñe un subalgoritmo RECURSIVO para obtener el factorial \(\left(n!\right)\) de un número entero no negativo. Dicho subalgoritmo debe recibir un número entero \((n)\) y debe devolver como resultado un número entero \(\left(n!\right)\) (¿qué valor debería devolver el subalgoritmo en caso de recibir un número entero negativo?).