Recursividad de cola

Introducción a la programación

I semestre, 2017

La recursividad...

...nos permite modelar la solución de muchos tipos de problemas.

… nos ayuda a desarrollar la capacidad de abstracción.

En la búsqueda de una solución a un problema, realizamos una abstracción de la realidad, para:

● “Visualizar” formas para descomponer el problema

● Llegar a un nivel de detalle suficiente para ser reflejado en un algoritmo.

Ilusionaria,Todos los derechos reservados, @20minutos.es

Recursividad

1. Según las evaluaciones pendientes:

● Recursividad de pila. (Todo lo visto hasta ahora)

● Recursividad de cola. ( A esta ya casi le entramos sólido )

2. Según el número de llamadas que se realicen:

● Recursividad simple. ( Factorial)

● Recursividad múltiple. ( Fibonacci)

3. Según la estructura de las llamadas:

● Recursividad directa. ( Factorial)

● Recursividad anidada. ( Ackerman)

● Recursividad indirecta. ( Solo la vamos a mencionar)

Recursividad directa

● Esta mezclada con los otros tipos de recursividad

● Involucra una única función que se llama a sí misma.

● Es la que hemos estado utilizando hasta ahora.

def funcion( x ): · · · · funcion( x' )

Recursividad indirecta

● Involucra más de una función para poder terminar el mecanismo de repetición.

● Más complicado de depurar.

● Pocos problemas hacen uso de este mecanismo.

● Hay que tener cuidado al utilizarla (pica, muerde y patalea).

def primera ( X ): · · · · segunda ( X' )

def segunda ( Y ): · · · · primera ( Y' )

Recursividad de cola

¿Dónde esta mi cola?¿Dónde esta mi cola?¿Dónde esta mi cola?

Un viejo uroboro de metal

Recursividad de cola

● Esta lava la ropa en lavadora, ya no ocupa la pila.

● Cuando llega a la condición de terminación, retorna de una el valor de la respuesta.

● No deja resultados pendientes en la pila para cuando se devuelva.

● Otros nombres:

– Recursividad de extremo de cola.– Recursividad extremo final.–

● Consiste de

● una función principal (para restricciones y casos especiales ).

● Una función auxiliar

(con un argumento extra para el resultado).

Cola contra pila

Pila Cola

No siempre ocupa la función auxiliar Acá la auxiliar es obligatoria.

La función auxiliar no siempre ocupa argumentos adicionales.

Acá siempre va al menos un argumento extra en la función auxiliar para el resutado.

La llamada recursiva va junto a una operación que se deja pendiente.

Acá no

Cuando pega con el caso base, tiene que devolverse y juntar todas las operaciones pendientes.

Cuando pega con el caso base o condición de parada, ya todo esta listo y solo falta devolver el resultado.

Ejemplos

Ejercicios

>>> fib(num)

>>> sumar_elementos(lista)

>>> sumatoria(ini, fin)

14

Las presentaciones para el curso IC-1800: "Introducción a la Programación" por Ing. En Computación Alajuela se distribuyen bajo una

Licencia Creative Commons Atribución-Compartir Igual 3.0 Costa Rica.

http://creativecommons.org/licenses/by-sa/3.0/cr/http://creativecommons.org/licenses/by-sa/3.0/cr/ *La licencia de la presentación no cubre las imágenes utilizadas*

Recursividad de cola

Introducción a la programación

I semestre, 2017

La recursividad...

...nos permite modelar la solución de muchos tipos de problemas.

… nos ayuda a desarrollar la capacidad de abstracción.

En la búsqueda de una solución a un problema, realizamos una abstracción de la realidad, para:

● “Visualizar” formas para descomponer el problema

● Llegar a un nivel de detalle suficiente para ser reflejado en un algoritmo.

Ilusionaria,Todos los derechos reservados, @20minutos.es

La imagen es un niño mirando una Matrioska, que son estas muñequitas rusas, que dentro tienen otra muñeca y otra y otra. ¿Recursividad?

Imagen de: http://www.20minutos.es/noticia/1209273/0/ilusionaria/cuentos/ninos-chernobil/#

Recursividad

1. Según las evaluaciones pendientes:

● Recursividad de pila. (Todo lo visto hasta ahora)

● Recursividad de cola. ( A esta ya casi le entramos sólido )

2. Según el número de llamadas que se realicen:

● Recursividad simple. ( Factorial)

● Recursividad múltiple. ( Fibonacci)

3. Según la estructura de las llamadas:

● Recursividad directa. ( Factorial)

● Recursividad anidada. ( Ackerman)

● Recursividad indirecta. ( Solo la vamos a mencionar)

Recursividad directa

● Esta mezclada con los otros tipos de recursividad

● Involucra una única función que se llama a sí misma.

● Es la que hemos estado utilizando hasta ahora.

def funcion( x ): · · · · funcion( x' )

Recursividad indirecta

● Involucra más de una función para poder terminar el mecanismo de repetición.

● Más complicado de depurar.

● Pocos problemas hacen uso de este mecanismo.

● Hay que tener cuidado al utilizarla (pica, muerde y patalea).

def primera ( X ): · · · · segunda ( X' )

def segunda ( Y ): · · · · primera ( Y' )

Recursividad de cola

¿Dónde esta mi cola?¿Dónde esta mi cola?¿Dónde esta mi cola?

Un viejo uroboro de metal

Representa la naturaleza cíclica de las cosas, el eterno retorno y otros conceptos percibidos como ciclos que comienzan de nuevo en cuanto concluyen

En un sentido más general simboliza el tiempo y la continuidad de la vida.

Se usa como representación del renacimiento de las cosas que nunca desaparecen, solo cambian eternamente.

Recursividad de cola

● Esta lava la ropa en lavadora, ya no ocupa la pila.

● Cuando llega a la condición de terminación, retorna de una el valor de la respuesta.

● No deja resultados pendientes en la pila para cuando se devuelva.

● Otros nombres:

– Recursividad de extremo de cola.– Recursividad extremo final.–

● Consiste de

● una función principal (para restricciones y casos especiales ).

● Una función auxiliar

(con un argumento extra para el resultado).

Cola contra pila

Pila Cola

No siempre ocupa la función auxiliar Acá la auxiliar es obligatoria.

La función auxiliar no siempre ocupa argumentos adicionales.

Acá siempre va al menos un argumento extra en la función auxiliar para el resutado.

La llamada recursiva va junto a una operación que se deja pendiente.

Acá no

Cuando pega con el caso base, tiene que devolverse y juntar todas las operaciones pendientes.

Cuando pega con el caso base o condición de parada, ya todo esta listo y solo falta devolver el resultado.

Ejemplos

Ejercicios

>>> fib(num)

>>> sumar_elementos(lista)

>>> sumatoria(ini, fin)

14

Las presentaciones para el curso IC-1800: "Introducción a la Programación" por Ing. En Computación Alajuela se distribuyen bajo una

Licencia Creative Commons Atribución-Compartir Igual 3.0 Costa Rica.

http://creativecommons.org/licenses/by-sa/3.0/cr/http://creativecommons.org/licenses/by-sa/3.0/cr/ *La licencia de la presentación no cubre las imágenes utilizadas*