View
224
Download
1
Category
Preview:
Citation preview
U11: Recursividad
Otra manera de hacer buclesDicen algunos pedagogos que conceptualmente mas sencilla
2
Datos
problema
simple
entero realcarácterbooleano
Ingeniero = Oreja+catalejomodelo
orde
nado
r
solución
asignación/referencia
Llamada procedimiento
whilefor Do while
if c: bloque1[ else: bloque2]
n bucles
0 o 1alternativas
1 o n0 o n
iterativo
n conocido
recursivo
n desconocido
case
gestión excepciones
Subprogramación
procedimiento
barajar complejidad
Proceso
hacer
función
Disponible en todos los lenguajesFrecuente en otros lenguajes y no disponible en PythonDisponible en Python, no frecuente en otros lenguajes
compuesto
arregloLista/tupla
EstructuratuplaNombre/record/clase
fichero
cadena
1secuencias
Recordatorio1: while permite repetir (iterar) un bloque de instrucciones. OJO programas que no acaban2: Cuando una pieza de código llama a otra, se apunta el contador del programa en la pila y se transfiere el control al subprograma llamado. Se almacenan en la pila los argumentos y variables locales. Al acabar el subprograma, se liberan las variables, se recoge el puntero de la pila y se reanuda la ejecución por donde iba antes de la llamada. 3: Para resolver problemas complejos, hasta ahora, hemos buscado subtareas diferentes, más sencillas, que cooperen.Recursividad:
enunciar la solución de un problema apoyándonos en uno semejante, pero más sencillo: xn = x · xn-1 ; x0 = 1
Diseño de un programa recursivo
• Enunciar el caso a resolver en términos de uno, o varios, casos “más sencillos”
• Identificar el (los) caso que se resuelve(n) directamente : Caso base• Garantizar que la descomposición se aproxime a un caso base
def potenciaR(x,n): """ numero,int-->numero OBJ: calcula x^n PRE: n>=0 """ if n==0: p=1 else: p = x*potenciaR(x,n-1) return p
print('2^8=', potenciaR(2,8))
base
recursivo
• Otra pieza de código realizará la primera llamada
Seguimiento de un programa recursivo""" imprime tupla recursivo """
def muestraTupla(pos,tupla): """int, tupla-->nada OBJ: muestra elementos de la tupla desde pos hasta el final PRE: 0<=pos<=len(tupla)""" if pos<len(tupla): print(tupla[pos],end='') muestraTupla(pos+1,tupla)
puente = 'J','V','S','D'muestraTupla(0,puente)
muestraTupla(0,puente) imprime J muestraTupla(1,puente)
imprime V muestraTupla(2,puente) imprime S muestraTupla(3,puente)
imprime D muestraTupla(4,puente)
4 no es menor que len(puente) Cierra 5ª copia de muestraTupla
Cierra 4ª copia de muestraTupla Cierra 3ª copia de muestraTupla
Cierra 2ª copia de muestraTuplaCierra 1ª copia de muestraTupla
Acaba el programa principal
Seguimiento de un programa recursivo
""" imprime tupla recursivo ""“
def muestraTupla(pos,tupla): """int, tupla-->nada OBJ: muestra elementos de la tupla desde pos hasta el final PRE: 0<=pos<=len(tupla)""" if pos<len(tupla): print(tupla[pos],end='') muestraTupla(pos+1,tupla)
""" ???????? """
def sorpresa(pos,tupla): """int, tupla-->nada OBJ: ????? PRE: 0<=pos<=len(tupla)""" if pos<len(tupla): sorpresa(pos+1,tupla) print(tupla[pos],end='')
Fibonacci en una piña
Enunciados recursivos
La sucesión de Fibonacci explica muchos fenómenos de la naturaleza (por ejemplo lee [Enzensberger 1997] y [wiki fibo]). Inicialmente se definió del siguiente modo: f(n)=f(n-1)+f(n-2) con f(1):=1, f(2)=1si bien actualmente se amplía con el término cero f(n)=f(n-1)+f(n-2) con f(0)=0, f(1):=1 Implementa un subprograma en Python que calcule el término n de la sucesión de Fibonacci.
def fiboR(n): """ int--> int OBJ:término n de fibonacci PRE: 0<=n<=30 """ if n==0:f=0 elif n==1: f=1 else: f = fiboR(n-1)+fiboR(n-2) return f
def fiboI(n): """ int--> int OBJ:término n de fibonacci PRE: 0<=n<=30 """ if n==0: f = 0 else: fn_2 = 0 f = 1 fn_1 = 1 for i in range(2,n+1): #range no incluye el extremo superior f = fn_1+fn_2 #preparo la siguiente pasada fn_2 = fn_1 fn_1 = f return f
f(n)=f(n-1)+f(n-2) con f(0)=0, f(1):=1
Eficiencia? def fiboR(n): """ int--> int OBJ:término n de fibonacci PRE: 0<=n<=30 """if n==0:f=0 elif n==1: f=1 else: f = fiboR(n-1)+fiboR(n-2) return f
f(n)=f(n-1)+f(n-2) con f(0)=0, f(1):=1
f1
f0
f2
f1
f0
f2f3
f1
f1
f0
f2f3
f1
f4
f1
f0
f2
f0
f2f3
f1
f4f5f6 f1
Algoritmia: evaluación teórica de costes de algoritmos, para comparar eficiencia
Evaluaciónexperimental eficiencia
f(n)=f(n-1)+f(n-2) con f(0)=0, f(1):=1
""" evaluando el tiempo que tarda Recursividad/Iteración """ from time import perf_counter print('n tR tI tR-tI porcentaje')for n in range (3,48,5): t0 = perf_counter() f = fiboR(n) tR = perf_counter()-t0 t0 = perf_counter() f = fiboI(n) tI = perf_counter()-t0 d = tR-tI print('%2d %9.4f %9.4f %9.4f %17.2f'%(n,tR,tI,d,d/tI*100))n tR tI tR-tI porcentaje 3 0.0000 0.0000 0.0000 29.41 8 0.0001 0.0000 0.0000 282.3513 0.0006 0.0000 0.0006 3125.6418 0.0066 0.0000 0.0066 31832.5623 0.0750 0.0000 0.0749 305345.1028 0.8195 0.0000 0.8195 3274965.3833 9.0982 0.0000 9.0982 32046908.4738 104.5935 0.0000 104.5934 278670814.15
Algoritmia
• evaluación teórica de costes de algoritmos• para comparar eficiencia de alternativos
• Tiempo• Memoria
• Complejidad computacional
Equivalencia def objetivoR(parametros): if q(parametros): objetivo=valorCasoBase else: proceso_no_recursivo objetivo=h(parametros,objetivoR(g(parametros)) return objetivo
def objetivoI(parametros): objetivo= valorCasoBase while not q(parametros): proceso no recursivo objetivo= h(parametros,objetivo) parámetros=g(parametros) return objetivo
Todos los problemas que tienen solución con una técnica se pueden resolver con la otra
Errores frecuentes: el nombre
Caso base
Caso recursivo Caso recursivo
Recursivo: Se llaman o contienen a si mismosHasta un cierto grado
Recurrente: Se repite con periodicidad
La RAE junio 2012
Errores frecuentes:
Bucle de más: la propia recursividad es un bucle Olvidar caso base No garantizar la convergencia
Pensar que es mejor solución
Resumen
• Recursividad=Repetición por autoreferencia• Potencia equivalente a la iteracíon• Suele consumir mas memoria y tiempo que la iteración• ¿Cuándo usar recursividad?
• Cuando simplifique mucho la programación y pruebas• Solo si el consumo de recursos no se dispara
Rosalía Peña (Univ. de Alcalá) 15
Se dispone de 3 soportes y n discos de diferente radio. Inicialmente los discos están apilados en orden creciente en el soporte A. Pasarlos al soporte B, quedando en el mismo orden en que están actualmente. El soporte C puede servir de auxiliar. Sólo se puede mover un disco cada vez. En cualquier soporte, en todo momento, cada disco debe tener un radio menor que el que tiene debajo.
Trabajo personal: Es el momento de jugar. Empieza con un caso sencillo: 2 discos de A a B usando C también sabes pasar 2 a C usando BPlanteaté pasar 3 discos de A a B usando C pasa 2 de A a C usando B, y el tercero a B y pasa 2 de C a B usando A…..
7.1 RECURSIVIDAD: Torres de Hanoi
A CB
Rosalía Peña (Univ. de Alcalá) 16
pasar (2,A,B,C):
pasar 1 de A (origen) a C (temp) con B
mover 1 de A (origen) a B (destino)
pasar 1 de C (temp) a B (destino) con B
7.1 RECURSIVIDAD: Torres de Hanoi
A CB
• pasar 1 de A a B con C• mover 1 de A a C• pasar 1 de B a A con C
• pasar 1 de C a A con B• mover 1 de C a B• pasar1 de A a B con C
pasar(num,origen,destino,temp)
A CB
pasar(3,a,b,c):
pasar 2 de A (origen) a C (temp)con B
mover 1 de A (origen) a B (destino)
pasar 2 de C (temp) a B(destino) con A
Rosalía Peña (Univ. de Alcalá) 17
7.1 RECURSIVIDAD: Torres de Hanoi
mover disco 1 de A a C mover disco 2 de A a B mover disco 1 de C a B mover disco 3 de A a C mover disco 1 de B a A mover disco 2 de B a C mover disco 1 de A a Cmover disco 4 de A a B mover disco 1 de C a B mover disco 2 de C a A mover disco 1 de B a A mover disco 3 de C a B mover disco 1 de A a C mover disco 2 de A a B mover disco 1 de C a B
¿con 4 para generalizar? pasar 4 de origen a destino usando temp
pasa( 2,A,B,C)
mover 1 de B a A
pasar(2,B,C,A)
Pasar 3 de origen a temp usando destino
pasar(3,A{origen}, C{temp},B{destino})
mover la cuarta de origen a destino
pasar 3 de temp a destino, usando origen
pasar 3,C{temp},B{destino}, A{origen})C
Recommended