Recursividad en los lenguajes de programación
Arthuroz39 de Mayo de 2013
602 Palabras (3 Páginas)517 Visitas
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 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.
...