Recursividad en los lenguajes de programación

Resumen:

En este artículo el autor describe los principios fundamentales que sustentan la recursividad en los lenguajes de programación.

Introducción:

El lenguaje Object Pascal tiene implementada una estructura de control de extraordinario valor, llamada recursividad, la cual permite que un procedimiento se llame a sí mismo como un subprocedimiento.

A través de esta poderosa herramienta se pueden expresar muchos algoritmos. Sin embargo es poco utilizada, motivado quizás por el desconocimiento de los principios fundamentales que la sustentan.

Este trabajo tiene como propósito describir los principios fundamentales de esta potente herramienta.

Desarrollo:

El concepto de recursividad está ligado, en los lenguajes de programación, al concepto de procedimiento o función. Un procedimiento o función es recursivo cuando durante una invocación a él puede ser invocado a su vez él mismo.

La recursividad es una de las formas de control más importantes en la programación. Los procedimientos recursivos son la forma más natural de representación de muchos algoritmos. Como ejemplo, elaboremos una función que nos permita calcular el factorial de un número:

Matemáticamente se define como factorial de un número n al producto de los enteros positivos desde 1 hasta n y se denota por n!

n! = 1 . 2 . 3 . 4 . 5 . . . (n – 2) (n – 1) n

también se define 0! = 1, de forma que la función está definida para todos los enteros no negativos. Así tenemos que:

0! = 1 1! = 1 2! = 1 . 2 = 2 3! = 1 . 2 . 3 = 6

4! = 1 . 2 . 3 . 4 = 24 5! = 1 . 2 . 4 . 5 = 120

y así sucesivamente.

Observe que:

5! = 5 . 4! = 5 . 24 = 120 6! = 6 . 5! = 6 . 120 = 720

esto se cumple para cualquier entero n positivo; o sea,

n! = n (n – 1) !

de acuerdo con esto, la función factorial se puede definir también como :

Si n < 2 entonces n! = 1

Si n 2 entonces n! = n (n – 1)!

Esta definición de n! es recursiva ya que se refiere a sí misma cuando invoca (n – 1) !

Luego nuestra función podría ser:

Function Factorial ( n : Integer ) : Integer;

begin

If n < 2 Then Factorial := 1

else Factorial := n * Factorial ( n – 1);

end;

Cuando esta función es invocada, por ejemplo, para hallar el factorial del número 3, se crean en la memoria de la computadora las siguientes instancias:

y al finalizar comienza el retorno a la invocación anterior efectuándose las acciones que habían quedado pendientes.

Observe

...