Lógica de Programación (28) - Recursividad

Infinite Will Wheatons!!!

Reza una regla muy conocida en el lenguaje que un término definido no puede ser incluido dentro de su propia definición. Sin embargo, en programación esta regla no existe y a dicha aparente "violación" se le conoce como recursividad y en esta lección vamos a aprender cómo funciona este útil y alucinante concepto de la programación.

Como ya hemos estudiado en todo este bloque, un subprograma puede llamar a cualquier otro subprograma y éste a otro y así sucesivamente; dicho de otro modo, los subprogramas se pueden anidar. Se puede tener:

A llamar_a B, B llamar_a C, C llamar_a D

Cuando se produce el retorno de los subprogramas, a la terminación de cada uno de ellos el proceso resultante será: 

D retornar_a C, C retornar_a B, B retornar_a A

Pero, ¿qué sucedería si los programas de una secuencia de este tipo son los mismos?

A llamar_a A

o bien

A llamar_a B, B llamar_a A

Esto, en primera instancia, parecería incorrecto. Sin embargo la gran mayoría de los lenguajes de programación incluyen mecanismos por los que un subprograma puede llamarse a sí mismo.

Una función o procedimiento que puede llamarse a sí mismo se llama recursivo. La recursividad es una herramienta muy potente, sobre todo en aquellas aplicaciones destinadas a hacer cálculos matemáticos o estadísticos. La recursividad también puede ser utilizada como una alternativa a las estructuras repetitivas. Si un problema puede definirse de modo natural en términos recursivos, entonces podemos programar una aplicación usando la recursividad para dicho problema.

Escribir un procedimiento o función recursivo es muy similar a escribir uno que no lo sea; sin embargo para evitar que la recursión continue indefinidamente es necesario que se incluya una condición de terminación.

Uno de los problemas más útiles para explicar la recursividad es el cálculo del factorial de un número (n!). Recordemos que el factorial se define de la siguiente manera:

n! = n * (n-1) * (n-2) * ... *3 * 2 * 1

Por ejemplo, el factorial de 5 se calcularía de este modo:

5! = 5 * 4 * 3 * 2 * 1

Sin embargo, observa que 4 * 3 * 2 * 1 es 4!, por lo que podríamos reescribir la expresión así:

5! = 5 * 4!

a la vez, observamos que 3 * 2 * 1 es igual a 3!, por lo que podría decirse que

4! = 4 * 3!

Si continuamos con dicha secuencia, podemos concluir que la función factorial es una función recursiva, pues para calcular el factorial de un número n requerimos calcular el factorial de n-1, es decir:

factorial <- n * factorial(n-1)

La definición de una función algorítmica sería entonces como sigue:

entero función factorial (entero n)

inicio

   si n = 0 entonces

      devolver (1)

   si_no

      devolver (n * factorial(n-1))

   fin_si

fin_función

Para demostrar cómo esta función recursiva calcula el factorial de 3, usemos el siguiente gráfico:

Observa que cada llamada a la función recursiva lleva como parámetro el número al que corresponda el turno. En la última llamada dicho número es 0, por lo que no se vuelve a llamara a la función recursiva sino que se retorna el valor de 1, con lo cual se van retornando sucesivamente los valores de las llamadas precedentes.

La recursividad es sin duda una de las herramientas más útiles con las que cuenta la programación y, aunque puede parecer confusa al principio, una vez que se comprende nos ayuda a crear aplicaciones más potentes, rápidas y con poco gasto de recursos de cómputo.

Con esta lección terminamos la introducción a los conceptos relativos a los subalgoritmos. En la siguiente lección voy a compartir una lista de ejercicios que pueden resolver para practicar todo lo relativo a las funciones y, después de eso, comenzaremos con la última sección de este curso de Lógica de Programación. ¡Hasta la próxima!

Enlace: Índice del curso