Pontificia Universidad Católica de Chile

Escuela de Ingenierı́a
Departamento de Ciencias de la Computación

Clase 20: Ejercicios Recursión

Rodrigo Toro Icarte (rntoro@uc.cl)

IIC1103 Introducción a la Programación - Sección 5

01 de Junio, 2015
Clases pasadas Ejemplos Ejercicios Propuestos

Recursión

2
Clases pasadas Ejemplos Ejercicios Propuestos

Recursión

¿Qué pasa si una función se llama dentro de sı́ misma?

1 def funcion () :
2 funcion ()
3
4 funcion ()

3
Clases pasadas Ejemplos Ejercicios Propuestos

Recursión

¿Qué pasa si una función se llama dentro de sı́ misma?

1 def funcion () :
2 funcion ()
3
4 funcion ()

... es una especie de loop infinito

3
Clases pasadas Ejemplos Ejercicios Propuestos

Recursión

¿Qué pasa si una función se llama dentro de sı́ misma?

1 def funcion () :
2 funcion ()
3
4 funcion ()

... es una especie de loop infinito

¿Qué hacı́amos para cortar el loop?

3
Clases pasadas Ejemplos Ejercicios Propuestos

Recursión

¿Cuál es la salida de este programa?

1 def funcion ( contador ) :

2 if ( contador == 0) :
3 return
4 print ( contador )
5 funcion ( contador -1)
6
7 funcion (5)

4
Clases pasadas Ejemplos Ejercicios Propuestos

Recursión

... y de este programa?

1 def funcion ( contador ) :

2 if ( contador == 0) :
3 return
4 funcion ( contador -1)
5 print ( contador )
6
7 funcion (5)

5
Clases pasadas Ejemplos Ejercicios Propuestos

Recursión

Definición
Recursión es una estrategia para solucionar problemas llamando
a una función dentro de si misma.

6
Clases pasadas Ejemplos Ejercicios Propuestos

Recursión

Definición
Recursión es una estrategia para solucionar problemas llamando
a una función dentro de si misma.

Ventajas:
Códigos más cortos.
Códigos más legibles.

6
Clases pasadas Ejemplos Ejercicios Propuestos

Recursión

¿Cuándo usar recursión?

7
Clases pasadas Ejemplos Ejercicios Propuestos

Recursión

¿Cuándo usar recursión?

1) Cuando un problema se puede dividir en subproblemas

idénticos, pero más pequeños.

2) Para explorar el espacio en un problema de búsqueda.

7
Clases pasadas Ejemplos Ejercicios Propuestos

Recursión

Dividir para conquistar

8
Clases pasadas Ejemplos Ejercicios Propuestos

Recursión

Ejemplo: Implemente una función que calcule n!

n! = n ∗ (n − 1)! 1! = 1 0! = 1

9
Clases pasadas Ejemplos Ejercicios Propuestos

Recursión

Ejemplo: Implemente una función que calcule n!

n! = n ∗ (n − 1)! 1! = 1 0! = 1

1 def factorial ( n ) :
2 if ( n <= 1) :
3 return 1
4 return n * factorial (n -1)
5
6 print ( factorial (5) )

9
Clases pasadas Ejemplos Ejercicios Propuestos

Recursión

10
Clases pasadas Ejemplos Ejercicios Propuestos

Recursión

11
Clases pasadas Ejemplos Ejercicios Propuestos

Recursión

1 def factorial ( n ) :
2 if ( n <= 1) :
3 return 1
4 return n * factorial (n -1)

Estructura solución recursiva:

Firma: Nombre y parámetros.
Casos bases.
Llamados recursivos.
Formar solución a partir de subsoluciones.

12
Clases pasadas Ejemplos Ejercicios Propuestos

Ejemplos

Importante: Estudien los ejemplos de la clase 08.

13
Clases pasadas Ejemplos Ejercicios Propuestos

Ejemplos

¿Qué hace el siguiente código?

1 def mystery (a , b ) :
2 if ( b == 0) : return 0
3 if ( b % 2 == 0) : return mystery ( a +a , b //2)
4 return mystery ( a +a , b //2) + a

14
Clases pasadas Ejemplos Ejercicios Propuestos

Ejemplos

Programe una función recursiva para verificar si una palabra es

un palı́ndromo.

15
Clases pasadas Ejemplos Ejercicios Propuestos

Ejemplos

Programe una función recursiva para verificar si una palabra es

un palı́ndromo.

1 def palindromo ( s ) :
2 if ( len ( s ) <= 1) :
3 return True
4 return ( s [0]== s [ -1]) and palindromo ( s [1: len ( s ) -1])

15
Clases pasadas Ejemplos Ejercicios Propuestos

Ejemplos

[Ex 2014-2] Tienes un tablero de n × n celdas blancas y

negras, distribuidas de cualquier manera. Una región blanca es
un conjunto contiguo máximo de celdas blancas: dos celdas
blancas son contiguas si tienen un borde común (si solo tienen
un vértice común, no son contiguas). Una región negra se define
similarmente.

16
Clases pasadas Ejemplos Ejercicios Propuestos

Ejemplos

El problema consiste en que dada una celda y un color, se pide

pintar de ese color toda la región a la que pertenece la celda.
Por ejemplo, si para el tablero de la figura anterior se especifica
la celda (3, 2) y el color gris, el resultado debe ser el tablerdo de
la derecha.

17
Clases pasadas Ejemplos Ejercicios Propuestos

Ejemplos

El problema consiste en que dada una celda y un color, se pide

pintar de ese color toda la región a la que pertenece la celda.
Por ejemplo, si para el tablero de la figura anterior se especifica
la celda (3, 2) y el color gris, el resultado debe ser el tablerdo de
la derecha.

Para ello, implementa la función pintar region(...), que

reciba los parámetros apropiados.
17
Clases pasadas Ejemplos Ejercicios Propuestos

Ejemplos

1 def pintar_region (t , p ) :
2 c = t [ p [0]][ p [1]]
3 t [ p [0]][ p [1]] = 2
4 for d in [[1 ,0] ,[ -1 ,0] ,[0 ,1] ,[0 , -1]]:
5 di = p [0]+ d [0]
6 dj = p [1]+ d [1]
7 if (0 <= di < len ( t ) and
8 0 <= dj < len ( t [0]) and
9 t [ di ][ dj ] == c ) :
10 pintar_region (t ,[ di , dj ])

18
Clases pasadas Ejemplos Ejercicios Propuestos

Ejemplos

Sea L una lista de números y n un número natural. ¿Se puede

formar n a partir de sumar elementos de L?

L=[5, 3, 9] y n=31 es True: 31 = 2×9 + 2×5 + 1×3.

19
Clases pasadas Ejemplos Ejercicios Propuestos

Ejemplos

Sea L una lista de números y n un número natural. ¿Se puede

formar n a partir de sumar elementos de L?

L=[5, 3, 9] y n=31 es True: 31 = 2×9 + 2×5 + 1×3.

1 def verificar_suma (L , n ) :
2 if ( len ( L ) == 0) :
3 return n == 0
4 for i in range ( n // L [0] + 1) :
5 if ( verificar_suma ( L [1:] , n - i * L [0]) ) :
6 return True
7 return False
8
9 print ( verificar_suma ([5 , 3 , 9] ,7) ) # >>> False
10 print ( verificar_suma ([5 , 3 , 9] ,31) ) # >>> True

19
Clases pasadas Ejemplos Ejercicios Propuestos

Ejemplos
¿Cómo retorno los factores que hacen posible la multiplicación?

Ejemplo: Para L=[5, 3, 9] y n=31 retornar [2, 1, 2].

20
Clases pasadas Ejemplos Ejercicios Propuestos

Ejemplos
¿Cómo retorno los factores que hacen posible la multiplicación?

Ejemplo: Para L=[5, 3, 9] y n=31 retornar [2, 1, 2].

1 def verificar_suma (L ,n , f =[]) :

2 if ( len ( L ) == 0) :
3 if ( n == 0) :
4 return []
5 return None
6 for i in range ( n // L [0] + 1) :
7 r = verificar_suma ( L [1:] , n - i * L [0])
8 if ( not r is None ) :
9 return [ i ] + r
10 return None
11
12 print ( verificar_suma ([5 , 3 , 9] ,7) ) # >>> None
13 print ( verificar_suma ([5 , 3 , 9] ,31) ) # >>> [2 ,1 ,2]

20
Clases pasadas Ejemplos Ejercicios Propuestos

Ejemplos

Paréntesis balanceados:

Genere un programa recursivo que indique si un string posee

paréntesis balanceados

21
Clases pasadas Ejemplos Ejercicios Propuestos

Ejemplos

Paréntesis balanceados:

Genere un programa recursivo que indique si un string posee

paréntesis balanceados

3 7
() ((
(())() )(
((())()) ((())((())

21
Clases pasadas Ejemplos Ejercicios Propuestos

Ejemplos

Reglas recursivas de construcción:

S → ""
S → (S)
S → SS

22
Clases pasadas Ejemplos Ejercicios Propuestos

Ejemplos

Reglas recursivas de construcción:

S → ""
S → (S)
S → SS

¿Cómo lo resolverı́an?

22
Clases pasadas Ejemplos Ejercicios Propuestos

Ejemplos

Caso base: (S → "")

s == ""

23
Clases pasadas Ejemplos Ejercicios Propuestos

Ejemplos

Caso base: (S → "")

s == ""

Casos recursivos: (S → (S))

s[0] == "(" and s[len(s)-1] == ")" and
par(s[1:len(s)-1])

23
Clases pasadas Ejemplos Ejercicios Propuestos

Ejemplos

Problema:
¿Cómo hacemos S → SS?
No sabemos dónde cortar S...

24
Clases pasadas Ejemplos Ejercicios Propuestos

Ejemplos

Problema:
¿Cómo hacemos S → SS?
No sabemos dónde cortar S...

Solución: Probemos todas las opciones de corte.

24
Clases pasadas Ejemplos Ejercicios Propuestos

Ejemplos

Problema:
¿Cómo hacemos S → SS?
No sabemos dónde cortar S...

Solución: Probemos todas las opciones de corte.

Casos recursivos: (S → SS)

par(s[:i]) and par(s[i:]) con i = 1...len(s)-1

24
Clases pasadas Ejemplos Ejercicios Propuestos

Ejemplos

1 def par ( s ) :
2 if ( s == " " ) :
3 return True
4 f = len ( s ) -1
5 if ( s [0] == " ( " and s [ f ] == " ) " and par ( s [1: f ]) ) :
6 return True
7 for i in range (1 , f ) :
8 if ( par ( s [: i ]) and par ( s [ i :]) ) :
9 return True
10 return False

25
Clases pasadas Ejemplos Ejercicios Propuestos

Ejemplos

Calculadora convencional:

Genere un programa recursivo que reciba un string con

operación aritmética (con paréntesis) y retorne su resultado.

26
Clases pasadas Ejemplos Ejercicios Propuestos

Ejemplos

Calculadora convencional:

Genere un programa recursivo que reciba un string con

operación aritmética (con paréntesis) y retorne su resultado.

Input Output
"3" 3
"(3+2)" 5
"((3+2)*5)" 25
"((3+2)*(5/2))" 12.5

26
Clases pasadas Ejemplos Ejercicios Propuestos

Ejemplos

Reglas recursivas de construcción:

S → d.
S → (S1 [op] S2).

... donde d es un número entero, S1 y S2 son operaciones

aritméticas bien formadas; y [op] es +, -, * o /.

27
Clases pasadas Ejemplos Ejercicios Propuestos

Ejemplos

Reglas recursivas de construcción:

S → d.
S → (S1 [op] S2).

... donde d es un número entero, S1 y S2 son operaciones

aritméticas bien formadas; y [op] es +, -, * o /.

¿Cómo lo resolverı́an?

27
Clases pasadas Ejemplos Ejercicios Propuestos

Ejemplos

Caso base: S → d (entero positivo)

s.isdigit()

28
Clases pasadas Ejemplos Ejercicios Propuestos

Ejemplos

Caso base: S → d (entero positivo)

s.isdigit()

Casos recursivos: S → (S1 [op] S2)

Necesitamos conocer la posición del operador.

28
Clases pasadas Ejemplos Ejercicios Propuestos

Ejemplos

Idea: Se debe cumplir con: S → (S1 [op] S2).

29
Clases pasadas Ejemplos Ejercicios Propuestos

Ejemplos

Idea: Se debe cumplir con: S → (S1 [op] S2).

Luego en S1 los paréntesis deben estar balanceados (se abren

tantos paréntesis como los que se cierran).

29
Clases pasadas Ejemplos Ejercicios Propuestos

Ejemplos

Idea: Se debe cumplir con: S → (S1 [op] S2).

Luego en S1 los paréntesis deben estar balanceados (se abren

tantos paréntesis como los que se cierran).

Algoritmo:
Recorrer S de izquierda a derecha (sin considerar primer
paréntesis).
Si veo un "(" sumo 1 a un contador.
Si veo un ")" resto 1 a un contador.
Si veo un operador y el contador es 0, entonces esa es la
posición buscada.

29
Clases pasadas Ejemplos Ejercicios Propuestos

Ejemplos

Una vez conocida la posición del operador, basta con:

Llamar recursivamente para obtener resultado del
operando S1.
Llamar recursivamente para obtener resultado del
operando S2.
Retornar S1 [op] S2

30
Clases pasadas Ejemplos Ejercicios Propuestos

Ejemplos
1 def calcular ( s ) :
2 if ( s . isdigit () ) :
3 return int ( s )
4 # Quito par é tesis externos
5 s = s [1: len ( s ) -1]
6 # Encontramos posici ó n operador
7 c = 0; pos = -1;
8 for i in range ( len ( s ) ) :
9 if ( s [ i ] == " ( " ) : c += 1
10 if ( s [ i ] == " ) " ) : c -= 1
11 if ( s [ i ] in [ ’+ ’ , ’ - ’ , ’* ’ , ’/ ’] and c ==0) :
12 pos = i ; break
13 # Retornamos el c á lculo
14 s1 = calcular ( s [: i ])
15 s2 = calcular ( s [ i +1:])
16 if ( s [ i ] == " + " ) : return s1 + s2
17 if ( s [ i ] == " -" ) : return s1 - s2
18 if ( s [ i ] == " * " ) : return s1 * s2
19 if ( s [ i ] == " / " ) : return s1 / s2
31
Clases pasadas Ejemplos Ejercicios Propuestos

Ejercicios Propuestos

1) Sin volver a ver las soluciones, intente resolver los ejemplos

puestos en la clase.

2) Implementa la función vueltos posibles(L,n) que retorna

el número de formas posibles en que podemos formar $n de
vuelto a partir de las monedas presentes en L. Por ejemplo
vueltos posibles([100],1000) deberı́a retornar 1, mientras
que vueltos posibles([1, 10, 50,100],1000) deberı́a
retornar 4.246.

32
Clases pasadas Ejemplos Ejercicios Propuestos

Ejercicios Propuestos

3) Crea un programa que verifique si un String corresponde a

una suma buen formada. Es decir, si cumple con:
S → entero positivo (i.e. s.isdigit() == True).
S → (S1+S2), donde S1 y S2 son sumas bien formadas.
Por ejemplo, las expresiones (1+7), 125, (23+(5+1)) y
((4+12)+(5+(6+7))) son sumas bien formadas, mientras que
(1+(2+4), (a+2), 4+ y 3+6 no lo son (notar que 3+6 no es una
suma bien formada por la ausencia de paréntesis).

Hint: Si el string S no es un número, para verificar si es de la

forma (S1+S2) puedes revisar cada uno de los signos + que
aparecen en S.

33