RECURSION
ESTRUCTURA DE DATOS
INTRODUCCION
• La recursión o recursividad es concepto amplio con muchas
variantes, y difícil de precisar con pocas palabras. Aparece en
numerosas actividades de la vida diaria; por ejemplo en una
fotografía donde se observa otra fotografía. Otro caso
ilustrativo es el que se presenta en los programas de televisión,
en los cuales un periodista transfiere el control de la noticia a
otro periodista que se encuentra en otra ciudad y este a su vez
hace lo mismo con un tercero, es un cambio o salto de control
que se hace de manera consecutiva.
Que es la Recursión
• Recursión o recursividad es la forma
en la cual se especifica un proceso
basado en su propia definición. La
recursión tiene esta característica
discernible en términos de
autorreferencialidad, Se dice que un
sistema tiene la propiedad de
recursividad Cuando contiene otros
sistemas dentro sí mismo. Podemos
entender por recursividad el hecho de
que un sistema, este compuesto a su
vez de objetos que también son
sistemas.
La recursividad se presenta como:
a) Directa: el programa o subprograma e llama
directamente a sí mismo. Por ejemplo:
“En la siguiente figura que veremos en la
siguiente diapositiva se Representa un
programa y en alguna parte de él aparece una
llamada así mismo.”
b) Indirecta: el subprograma llama a otro
subprograma, y é te, en algún momento,"
"llama nuevamente al primero. Por ejemplo, en
la figura el subprograma P llama al
subprograma Q y é te, a u vez, invoca al
primero; e decir, el control regresa a P."
PRESENTACION
En toda definición recursiva de un problema siempre e deben establecer dos pasos
"diferente y muy importante ; el paso básico y el paso recursivo. El primero uno o
vario , dependiendo del problema, e utiliza como condición de parada o fin de la
recursividad. A é te llegamos cuando encontramos la solución del problema o
cuando decidimos que ya no vamos a seguir, porque no están dada la condicione
para hacerlo.
SEGUNDO PASO
“Paso segundo, por otra parte, propicia la recursividad. Se pueden presentar uno o varios,"
nuevamente dependiendo del problema a resolver.
"Cuando se analiza la solución recursiva de un problema es importante determinar con
precisión cuáles serán los pasos básico y recursivo. En cada vuelta del ciclo es importante
que nos acerquemos cada vez más a la solución del problema, o sea, al paso básico. Si esto
no ocurre, entonces podemos estar ante un ciclo extraño. Es decir, el problema estaría mal
definido y, en tal caso, la máquina se quedaría ejecutando por tiempo indefinido el
programa en que estuviera, y sólo terminaría al agotarse la memoria."
A continuación se presentan algunos ejemplos que nos pueden ayudar a compren der más
rápidamente el concepto recursión.
FACTORIAL DE UN NUMERO
• El factorial de un numero entero positivo N se define como el
producto de los números comprendidos entre 1 y n por el
factorial de (n – 1), así aparece el concepto de recursión. La
expresión n! simboliza el factorial de N. A continuación se
ilustra el caso
Ejemplos
• Al calcular, por ejemplo, el factorial de 4, decimos que 4! Es
igual a 4* 3!. Al factorial de 3, lo calculamos como 3* 2!. Al
factorial de 2. como 2* 1!, y así sucesivamente hasta llegar a
un paso básico que detiene la recursividad. Llegamos a definir,
entonces el factorial de un numero n en términos del factorial
del numero (n-1).
Algoritmo factorial
• Cuando se realiza una llamada recursiva, se utiliza, en forma
implícita, una estructura tipo pila para almacenar la
instrucciones pendientes de ejecutar, con todos los valores que
tienen las variables o constantes en ese momento.
EJEMPLOS
"Observe que en la pila el número que se encuentra entre corchetes en la primera columna de la
izquierda hace referencia a la llamada recursiva que se realiza. Este símbolo permite observar el
orden en que se realizan las llamadas recursiva . Por ejemplo, (1) expresa que a e la primera
llamada recursiva, (2) reprenta la segunda llamada y a í sucesivamente. Por otra parte, el mismo
número entre corchetes a la izquierda relaciona"
l a llamada recursiva con el valor que ingresa al algoritmo en cada llamada.
"A continuación se presenta la variante iterativa del cálculo del factorial. Nunca hay que
descartar las variantes iterativa de la solución de u n problema, porque aun cuando éste
puede resolver naturalmente de forma recursiva es importante tener siempre tener en cuenta que
la recursión necesita de una pila para un funcionamiento y que ésta consume espacio de
memoria. En algunos lenguaje de programación , el espacio dedicado a la pila muy
pequeño, por lo que si el problema que se intenta resolver requiere de una cantidad de espacio
mayor -Pila- que la que ofrece el lenguaje, el problema no podrá resolver por falta de memoria.
En tal caso, una forma para remediar este inconveniente utilizando iteratividad en lugar de
recursividad."
Ejemplo de algoritmo
• Se puede decir que la recursividad es una técnica de
programación bastante útil y muy interesante de estudiar. A
través de los ejemplos que el individuo pueda revisar,
aprenderá con más rapidez y sencillez lo que es programar
recursivamente e incluir esta técnica cuando se le presente un
problema como los que fueron mencionados anteriormente.
