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