BotonMenu
BotonIndice

Visita : http://www.conoce3000.com
Paypal : https://www.paypal.me/conoce3000/1

PASCAL CON FREE PASCAL

PASCAL CON FREE PASCAL

PASCAL CON FREE PASCAL


6. FUNCIONES, PROCEDIMIENTOS Y UNIDADES.
6.6. RECURSIVIDAD.
6. FUNCIONES, PROCEDIMIENTOS Y UNIDADES.
6.6. RECURSIVIDAD.
6. FUNCIONES, PROCEDIMIENTOS Y UNIDADES.
6.6. RECURSIVIDAD.

SIGUIENTE

SIGUIENTE

SIGUIENTE


‒ Recursividad.

La recursividad sucede cuando un procedimiento o función se ejecuta a sí mismo. Cada vez que el procedimiento o función se ejecuta a sí mismo, se crean sus parámetros y variables locales en la Pila, por cada ejecución que se realice. Cuando se hace un procedimiento o función con recursividad, se debe usar una condición para detener las ejecuciones sucesivas del procedimiento ó función. Por ejemplo el siguiente programa:


Descargar
{$codepage UTF8}

PROCEDURE Infinito;
  Begin
    Writeln('a');
    Infinito
  End;
  
BEGIN
  Infinito;
  Writeln('FIN del programa')
END.
Código fuente 14: Recursividad Infinito.
Descargar

Realiza una recursividad del procedimiento Infinito, pero el programa se ejecutará hasta que este deje de funcionar por falta de memoria en la Pila. El programa deja de funcionar cuando la Pila se llene, finalizando el programa bruscamente con un mensaje de error, impidiendo que se muestre el mensaje : FIN del programa.

Debido a que el procedimiento se ejecuta sucesivamente a sí mismo, sin ninguna condición entonces no existe la posibilidad de terminar con el procedimiento infinito que ejecuto al anterior, y eso hace que no se pueda destruir o liberar espacio en la Pila.

El siguiente programa es parecido al anterior, pero usa una condición para controlar la recursividad. A continuación el ejemplo:


Descargar
{$codepage UTF8}

PROCEDURE Finito(c:integer);  
  Begin
    Writeln(c);
    c+=1;    
    if c<=9 then  Finito(c)
  End;
  
BEGIN
  Finito(1);
  Writeln('FIN del programa')
END.
Código fuente 15: Recursividad controlada por una condición.
Descargar

En este caso el procedimiento Finito, usa una condición y se ejecuta asimismo sólo 9 veces, evitando que la pila se llene y el programa pueda continuar con su funcionamiento, mostrando el mensaje: FIN del programa.

La recursividad que hemos visto se conoce como recursividad simple o directa, existe otra caso de recursividad, que se conoce como recursividad indirecta o circular, esta se produce cuando un procedimiento o función ejecuta a otra, que a su vez terminará ejecutando de nuevo a la primera función o procedimiento. El siguiente programa muestra un ejemplo de recursión circular o indirecta:


Descargar
{$codepage UTF8}

PROCEDURE ProcedimientoB(c:byte);forward;
  
PROCEDURE ProcedimientoA(c:byte);
  Begin
    Write(c:3);
    if (c > 0) then ProcedimientoB(c);     
  End;

PROCEDURE ProcedimientoB(c:byte);
  Begin
    ProcedimientoA(c-1);
  End;

BEGIN
  ProcedimientoA(20);
END.
Código fuente 16: Recursividad indirecta o circular.
Descargar

Se puede observar que he declarado con anterioridad la cabecera del procedimientoB, con una palabra reservada forward, que le indica al compilador que este procedimiento se definirá más adelante en el programa.

Debido a que el procedimientoB se ejecuta dentro del ProcedimientoA, es necesario declararlo antes que B, pero no podríamos hacerlo porque el procedimientoB, necesita ejecutar al procedimientoA. Es por eso que se escribe sólo el encabezado del ProcedimientoB con la palabra reservada forward, para de esta manera poder usarlo en el ProcedimientoA. Obviamente se debe de escribir después el ProcedimientoB completo, ya que el uso de la palabra reservada forward, le indica al compilador que ese procedimiento se escribirá más adelante en el código fuente.

Algunos problemas matemáticos se pueden implementar con el uso de la recursividad simple o directa, como ejemplo tenemos el cálculo de factoriales, obtener el término n de la serie de Fibonacci, y el algoritmo recursivo de Ackermann. A continuación la implementación de los problemas matemáticos mencionados:


Descargar
{$codepage UTF8}

FUNCTION Factorial(n:qword):qword;
  Begin
    if (n=0) then Factorial:=1
             else Factorial:=n*Factorial(n-1)
  End;
  
FUNCTION Fibonacci(n:qword):qword;
 Begin
  if (n<2) then Fibonacci:=n
  else Fibonacci:=Fibonacci(n-1)+Fibonacci(n-2);
 End;

FUNCTION Ack(m,n:qword):qword;
  Begin
    if (m=0) then Ack:=n+1  
    else if (n=0) then  Ack:=Ack(m-1,1)    
    else Ack:=Ack(m-1,Ack(m,n-1))
  End;  
  
BEGIN
  Writeln(Factorial(16));  
  Writeln(Fibonacci(20)); 
  Writeln(Ack(3,1))
END.
Código fuente 17: Ejemplos de recursividad, Factorial, Fibonacci y Ackerman.
Descargar

Las descripciones recursivas en las matemáticas se usan para describir algo, de tal manera que un ser humano sea capaz de entenderlo. Es por eso que son descripciones breves y concisas, para que se comprendan con relativa facilidad. Pero, cuando usamos la recursividad en la programación, nos encontramos con una serie de factores como la falta de memoria en la Pila, que impiden poner en práctica las descripciones recursivas. En esos casos es recomendable convertir una función o procedimiento recursivo en una función o procedimiento iterativo, siempre y cuando sea posible. A modo de ejemplo el cálculo del término n de la serie fibonacci en una función iterativa:


Descargar
{$codepage UTF8}

FUNCTION Fibonacci(n:qword):qword;
 var i,j,c,aux:integer;
 Begin
  i:=1;
  j:=0;
  for c:=1 to n do
   Begin
     aux:=j+i;
     i:=j;
     j:=aux;     
   End;
  Fibonacci:=j  
 End;

BEGIN
  Writeln(Fibonacci(20));
END.
Código fuente 18: Ejemplo iterativo de fibonacci.
Descargar

Otros ejemplos de recursividad directa o simple para mencionar serían: calcular el Máximo Común Divisor, las Torres de Hanoi, la suma de los elementos de un arreglo, Quick Sort, etc.




SIGUIENTE
SIGUIENTE
SIGUIENTE



 
‒ Comentarios y sugerencias.

Agradezco de antemano, todo comentario, sugerencia, y donativo (a través de Paypal me), que ayude a mejorar los contenidos educativos de Conoce 3000. Además, cualquier pregunta o duda que tengas lo puedes hacer por este medio. Pero, todo contenido que pueda resultar ofensivo, malicioso, racista, sexista, discriminatorio, obsceno, vulgar será eliminado.


Comments System WIDGET PACK






PORTADA |  INTERESANTE |  APUNTES |  LIBROS |  GALERIA


Creative Commons License


Todos los textos, imágenes y videos de Conoce3000 estan colocados bajo una licencia : Creative Commons Reconocimiento-NoComercial 3.0 Unported License.