En este artículo el autor describe los principios
fundamentales que sustentan la recursividad en los lenguajes de
programació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.
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 cómo una nueva invocación a la
función Factorial, cuando aún no se ha terminado la
invocación anterior, no afecta el valor de la variable
local n que se creó en la invocación anterior. Esto
es esencialmente el principio fundamental de las funciones o
procedimientos recursivos, y que hace de estos un mecanismo
cualitativamente superior; cada instancia interrumpida de la
función o del procedimiento, por una llamada a otro
procedimiento o función, conserva sus datos locales,
aún cuando el procedimiento o función pueda ser
nuevamente invocado.
Al escribir un procedimiento o una función
recursiva es esencial que se incluya, en el procedimiento o
función, una condición de terminación para
evitar que la recursión continué indefinidamente.
Mientras la condición de terminación permanezca
insatisfecha, el procedimiento o función se
invocará a sí mismo, del igual modo que
invocaría a cualquier otro procedimiento o
función.
Ejemplos:
La siguiente función tiene como entrada un
número y el exponente y responde con la potencia del
número:
Function Potencia ( Base, Exponente : Integer ) :
Integer;
begin
If Exponente = 1 Then Potencia:= Base
else Potencia := Base * Potencia ( Base,
Exponente – 1);
end;
Al ejecutar Potencia (2,3) obtenemos como respuesta 8.
Analicemos en un esquema la corrida de esta
función:
Cuando se cumple la condición 1 = 1 la
función Potencia (2, 1) se detiene, y responde con el
valor 2, que en la función anterior Potencia (2, 2), es
multiplicado por 2, razón por la cual esta función
responde con 4 a la función Potencia (2, 3) donde es
multiplicado por 2 y entrega como respuesta 8.
La siguiente función acepta una línea de
texto y la
devuelve en orden inverso.
Function Invertir ( Linea : String ) :
String;
Var
I : Integer;
begin
I := Length (Linea);
If I <> 0 Then Invertir := Copy (Linea, I, 1) +
Invertir (Copy (Linea, 1, I – 1))
end;
Al invocar Invertir (PAZ) obtenemos como respuesta
ZAP.
Veamos el esquema de salida:
ZAP
Invertir (PAZ);
Var
I : Integer;
begin
I := 3;
If 3 <> 0 Then Invertir := Z + Invertir
(PA);
end;
Invertir (PA);
Var
I : Integer;
AP begin
I := 2;
If 2 <> 0 Then Invertir := A + Invertir
(P);
end;
Invertir (P);
Var
I : Integer;
P begin
I := 1;
If 1 <> 0 Then Invertir := P + Invertir
(‘ ‘);
end;
Invertir (‘ ‘);
Var
I : Integer;
begin
I := 0;
If 0 <> 0
end;
Cuando deja de cumplirse la condición 0 <>
0, la función Invertir (‘ ‘) se detiene y le
responde con vacío a la función Invertir (P), esta
función concatena el carácter vacío con el
carácter P, y responde con P a la función Invertir
(PA) donde se forma la cadena AP que le es entregada como
respuesta a la función Invertir (PAZ) que al concatenarla
con Z devuelva como resultado la cadena ZAP.
Para finalizar es bueno aclarar que a pesar de que la
recursión permite representar en forma clara y elegante
muchos algoritmos, sin embargo, el costo de memoria y
tiempo que
requiere su realización, puede implicar que para
determinados algoritmos no sea conveniente su utilización
por lo que cada problema debe ser considerado según sus
propios méritos individuales.
No se trata de querer aplicar siempre la
recursión, hay problemas que
es mucho más ventajoso resolverlos por una vía no
recursiva.
El conocimiento
de los principios fundamentales de la recursividad evita evadir
su utilización cuando su aplicación sea conveniente
para un determinado problema.
El uso de la recursividad es particularmente conveniente
para aquellos problemas que pueden definirse de modo natural en
términos de recursividad.
Katrib Mora, Miguel. Lenguajes de programación y
Técnicas de compilación.– Ciudad de
la Habana : Editorial Pueblo y Educación,
1988
Gottfried, Byron S. Programación en Pascal.–
Ciudad de la Habana : Editorial Pueblo y Educación,
1989
Lipschutz, Seymour. Estructura de
datos.– Ciudad de la Habana : Edición
Revolucionaria, 1989
Autor:
Asistente Juan Antonio Fonseca
Hernández