recursividad terminal

RECURSIVIDAD TERMINALPresentación 2.

¿ QUE ES LA RECURSIVIDAD?

La recursividad es una técnica de programación,que consiste en que una serie de instrucciones se

repiten como una subtarea de la tarea principal, es decir, las funciones, procesos o rutinas se llaman a sí mismos cada vez que lo requieran y se ejecutan repetidas veces hasta que se satisface una condición específica.

RECURSIVIDAD

La recursividad es un proceso muy útil a la hora de programar, pero en ocasiones, el uso de este tiene un costo computacional alto, debido a las constantes llamadas a la misma función o rutina y muchas veces estas llamadas consumen demasiada memoria.

RECURSIVIDAD TERMINAL

En algunos algoritmos recursivos, se puede implementar un caso de recursividad especial llamado recursividad terminal, (también conocido como recursividad por cola), la cual es una técnica para optimizar la recursividad eliminando las constantes llamadas recursivas

“La recursividad terminal o por cola es cuando la llamada recursiva es la última instrucción de la función.”


características de la recursividad terminal.

*las funciones deben cumplir la condición que en la parte que realiza la llamada a la función, no debe existir ninguna otra sentencia.

*el compilador o interprete, tratan a la función recursiva como una función iterativa


Una ventaja de la recursividad por cola es que podemos evitar la sobrecarga de cada llamada a la función y nos evitamos el gasto de memoria de pila.

.

*pila de llamadas es donde se almacena los valores de las variables de las subrutinas, y el stack overflow (desbordamiento de pila) es cuando la memoria ya no es sufiente para almacenar todos los datos

Con una función de recursividad terminal se puede evitar lo que se conoce como stack overflow, que ocurre cuando la pila de llamadas (en ingles call stack) consume mucha memoria

EJEMPLOS

A continuación se muestra un programa que calcule el factorial de un numero usando la recursividad normal.

*funcion recursiva

* condicion* los valores que debe regresar*en el return se vuelve a llamar la funcion

*funcion principal

*captura de dato

*llamada de la funcion

EJEMPLOS

Ahora se muestra el mismo programa, que calcula el factorial de una función, pero usando la recursividad terminal o de cola

*funcion recursiva terminal•Se le agrega un contador, para que el proceso se realice alli mismo y no tener que llamar a la funcion de nuevo

• aquí se ase una funcion para que la estructura del main quede igual que en el otro ejemplo

•Funcion main con captura de dato y llamada de funcion

COMPARANDO

Recursividad normal Recursividad de cola


Una función recursiva normal se puede convertir a funcion recursiva termianl usando en la función original un parámetro adicional, usado para ir guardando un resultado de tal manera que la llamada recursiva ya no tiene una operación pendiente.

También se usa una función adicional para mantener la sintaxis de como llamamos normalmente a la función. En el caso del factorial, para seguir llamando a la función de la forma fact(n).


Si estos dos programas se corren, ambos funcionaran y nos darán un resultado correcto, pero entre mas grande sea el numero que se desea calcular, mas cerca estará el programa de recursión normal de “tronar”, ya que el numero que se ocupe será el numero de veces que se estará autollamado la función, cargando así la memoria, con el riesgo de un desbordamiento.


La recursión de cola es importante para algunos lenguajes de alto nivel, En especial en idiomas funcional y los idiomas miembros del familia Lisp.


En estos idiomas la recursión de cola es la forma más utilizada comúnmente (y ha veces la única forma disponible) de ejecución de la iteración.

La especificación del lenguaje del sistema que exige las llamadas de la cola para ser optimizado, para que no crezca la pila. Las llamadas de la recursividad Tail también puede ser utilizado en Perl, con una variante del "goto" La declaración que toma un nombre de función.


En muchos casos, hacer una función recursiva por la cola (tail-recursive) es posible empleando técnicas adecuadas de programación.

Siempre que esto se logre podemos esperar un incremento significativo en la eficiencia de los programas.


Se pude decir que la principal característica de la recursividad tail es que la llamada recursiva esta en la ultima posición ejecutada del procedimiento.

Otros nombres de la Recursividad Tail:

Recursividad terminal. Recursividad de cola. Recursividad de extremo final. Recursividad de extremo de cola.

recursividad terminal

Education