cc 1002: introduccióna la programación recursión

CC 1002: Introducción a la ProgramaciónRecursión

Nelson Baloian, José A. Pino

Recursión

• Dícese de un proceso o función que se define a partir de si misma.

• La idea es dividir el problema en instancias mas simples y pequeñas del mismo problema.

• Similar a la inducción.

Factorial

• El factorial de un número n se define como:• ! · 1 · 2 ·. . .· 2 · 1

• Se puede definir recursivamente de la siguiente manera

! 1 0· 1 ! 0

Factorial en Python

Operación de Factorial recursivo

f(4)=4*f(3)f(3)=3*f(2)

f(2)=2*f(1)f(1)=1*f(0)

← f(0)=1← f(1)=1 * 1=1

← f(2)=2 * 1=2← f(3)=3 * 2=6

f(4)=4* 6=24

Potencia (recursivamente)

• Definición recursiva de potencia

• Calculo :

1 0· 0

2 2 · 22 · 22 · 2 · 22 · 2 · 2 · 22 · 2 · 2 · 2 · 2

2 · 2 · 2 · 2 · 116

Potencia (recursivamente)

1 0· 0

Caso Base

Caso Recursivo

En Python

Solución más eficiente

1 0 ·

/ · /

Podemos realizar mas de una llamada recursiva

Podemos tener masde un caso recursivo

En Python

Notar que se realizan varios llamados recursivos que producen el mismo resultado!

¿Se puede hacer mejor?Si

Calculamos el valor recursivamente 1 vez

Luego reutilizamos este resultado en donde sea necesario.

Los Números de Fibonacci

0 01 1

2Podemos tener masde un caso base

Secuencia de números de la forma:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55…

Cada elemento es la suma de los 2 anteriores!

Fibonacci (paréntesis)

Patrón de crecimiento de las ramas de una planta

En Python

Funciones que no retornan valores

Si llega a este punto, la función retorna, y no ejecuta las instrucciones que siguen mas abajo.

El llamado recursivo a si misma, permite simular un ciclo de ejecución hasta que el usuario adivine (o se rinda)

Modulo Turtle (Tortuga)

• Modulo de Python que provee funciones para dibujar en pantalla.

• Algunas funciones provistas son:• turtle.forward(size): La tortuga se mueve una

distancia size en su dirección actual.• turtle.left(angle): La tortuga gira angle grados a la

izquierda.• turtle.right(angle): La tortuga gira angle grados a la

derecha.

Modulo Turtle (Tortuga)

• Modulo de Python que provee funciones para dibujar en pantalla.

• Algunas funciones provistas son:• turtle.done(): Indica que terminamos de dibujar.• turtle.resetscreen(): Borra todo dibujo realizado por

la tortuga.• turtle.penup(): Levanta el lápiz de dibujo. Permite

mover la tortuga sin dibujar.• turtle.pendown(): Baja el lápiz de dibujo. Permite

mover la tortuga dibujando su camino.

Modulo Turtle (Ejemplos)>>> import turtle>>> turtle.forward(100)

Modulo Turtle (Ejemplos)>>> import turtle>>> turtle.forward(100)>>> turtle.left(90)

Modulo Turtle (Ejemplos)>>> import turtle>>> turtle.forward(100)>>> turtle.left(90)>>> turtle.forward(100)

Modulo Turtle (Ejemplos)>>> import turtle>>> turtle.forward(100)>>> turtle.left(90)>>> turtle.forward(100)>>> turtle.left(90)>>> turtle.penup()>>> turtle.forward(100)

Modulo Turtle (Ejemplos)>>> import turtle>>> turtle.forward(100)>>> turtle.left(90)>>> turtle.forward(100)>>> turtle.left(90)>>> turtle.penup()>>> turtle.forward(100)>>> turtle.left(90)>>> turtle.pendown()>>> turtle.forward(50)

Modulo Turtle (Funciones)

>>> Cuadrado(100)

Fractales

• Objeto geométrico cuya estructura se repite a diferentes escalas.

• Es decir, su forma esta hecha de copias mas pequeñas de su misma figura.

Fractales

Fractales

Fractales

Copo de nieve de Koch

• Fractal cuya forma es similar a un copo de nieve.

Copo de nieve de Koch

Base Nivel 1 Nivel 2 Nivel 3

Generador

Copo de nieve de Koch

• Construcción del copo de nieve:

• Repetir la figura inicial (generador) sobre si mismo tantos niveles como se desee recursivamente.

• Repetir esta construcción 3 veces sobre la figura base (un triangulo)

1

2

3

4

0

Copo de nieve (Algoritmo)

• Para dibujar un segmento:• Dibujar recursivamente el fractal en el segmento 1• Girar 60 grados a la izquierda• Dibujar recursivamente el fractal en el segmento 2• Girar 120 grados a la derecha• Dibujar recursivamente el fractal en el segmento 3• Girar 60 grados a la izquierda• Dibujar recursivamente el fractal en el segmento 4

1

2 3

4

Copo de nieve (Código)

Copo de nieve (Código)

>>> snowflake(320,3)

Las torres de Hanoi• Puzzle matemático que consiste en mover todos los discos de una

vara a otra, bajo ciertas restricciones. El juego consta de una plataforma con tres varas y n discos puestos en orden decreciente de tamaño en una de ellas. El objetivo del juego es mover todos los discos de una vara a la otra, de forma que al final se mantenga el mismo orden.

• Las reglas del juego son las siguientes:• Solo 1 disco puede ser movido a la vez.• No puede haber un disco más grande encima de uno más pequeño.• Un movimiento consiste en mover un disco en la cima de una pila de discos

hacia otra pila de discos puestos en otra vara.

• Nos interesa saber cuantos movimientos son necesarios para resolver el juego

Clave: induccion

• Se trata de definir # hanoi int -> int# recibe el numero de argollas y responde con la # cantidad de movimientos necesarios para llevarlas a la estaca de mas a la derecha

def hanoi(n) :. . .

• Si tenemos un solo disco basta moverlo de la primera a la ultima barra

• Supongamos que sabemos como calcular hanoi(n-1), ¿ podemos escribir hanoi(n) en funcion de ella ?

Clave: induccion• Primero necesitamos mover los n−1 discos anteriores a otra

vara, lo cual nos toma hanoi(n-1) movimientos.• Luego, debemos mover el disco más grande de su vara a la

desocupada, esto nos toma 1 movimiento.• A continuación, debemos volver a mover los n − 1 discos

restantes para que queden encima del disco grande que acabamos de mover. Esto nuevamente nos toma hanoi(n-1) movimientos.

• En total, necesitamos 2× hanoi(n-1) +1 movimientos para n discos

El programa en Python

Ejercicios Propuestos

• def suma(x,y) #x + (x+1) + … + y x <= y• def permutaciones(x,y) #x!/(x-y)!• def combinaciones(x,y) #x!/(y!(x-y)!)

• def inverso(x) #inverso(1234) entrega 4321

• Para la función potencia, agregar el caso cuando el exponente es negativo.

(martes)

Leer capítulo 7 del apunte!!

Para la próxima clase

Felices Fiestas PatriasLes desea su

equipo docente