fundamentos de programaciónpepe/doc/fprg/07-recursion.ppt.pdf22.12.2010 argumentos y variables...
TRANSCRIPT
![Page 1: Fundamentos de Programaciónpepe/doc/fprg/07-recursion.ppt.pdf22.12.2010 argumentos y variables locales Se crean con la llamada Desaparecen al acabar Si hay varias llamadas simultáneas,](https://reader035.vdocumento.com/reader035/viewer/2022070909/5f8e023e38e3cb00e53e7fa1/html5/thumbnails/1.jpg)
Fundamentos de Programación
Métodos métodos recursivos
José A. Mañas <[email protected]> Dpto. de Ingeniería de Sistemas Telemáticos
http://www.lab.dit.upm.es/~fprg/ 22.12.2010
![Page 2: Fundamentos de Programaciónpepe/doc/fprg/07-recursion.ppt.pdf22.12.2010 argumentos y variables locales Se crean con la llamada Desaparecen al acabar Si hay varias llamadas simultáneas,](https://reader035.vdocumento.com/reader035/viewer/2022070909/5f8e023e38e3cb00e53e7fa1/html5/thumbnails/2.jpg)
22.12.2010
anatomía
double distancia (Punto q) { double dx= x – q.getX(); double dy= y – q.getY(); return Math.sqrt(dx*dx + dy*dy); }
nombre tipo del
resultado argumentos
variables locales
resultado final
cuerpo
cabecera
2
![Page 3: Fundamentos de Programaciónpepe/doc/fprg/07-recursion.ppt.pdf22.12.2010 argumentos y variables locales Se crean con la llamada Desaparecen al acabar Si hay varias llamadas simultáneas,](https://reader035.vdocumento.com/reader035/viewer/2022070909/5f8e023e38e3cb00e53e7fa1/html5/thumbnails/3.jpg)
22.12.2010
argumentos y variables locales
Se crean con la llamada Desaparecen al acabar
Si hay varias llamadas simultáneas, cada llamada tiene sus variables propias
3
![Page 4: Fundamentos de Programaciónpepe/doc/fprg/07-recursion.ppt.pdf22.12.2010 argumentos y variables locales Se crean con la llamada Desaparecen al acabar Si hay varias llamadas simultáneas,](https://reader035.vdocumento.com/reader035/viewer/2022070909/5f8e023e38e3cb00e53e7fa1/html5/thumbnails/4.jpg)
22.12.2010
factorial recursivo
Un método puede llamarse a si mismo int factorial (int n) {
if (n < 1) return 1; return n * factorial(n-1); }
Hay que cerciorarse de que no es un círculo vicioso int factorial (int n) {
if (n == 0) return 1; return n * factorial(n-1); }
4
![Page 5: Fundamentos de Programaciónpepe/doc/fprg/07-recursion.ppt.pdf22.12.2010 argumentos y variables locales Se crean con la llamada Desaparecen al acabar Si hay varias llamadas simultáneas,](https://reader035.vdocumento.com/reader035/viewer/2022070909/5f8e023e38e3cb00e53e7fa1/html5/thumbnails/5.jpg)
22.12.2010
recursión
Métodos que se llaman a sí mismos similares a las pruebas por inducción
Necesitan una condición de parada converger en cada paso hacia la parada
5
![Page 6: Fundamentos de Programaciónpepe/doc/fprg/07-recursion.ppt.pdf22.12.2010 argumentos y variables locales Se crean con la llamada Desaparecen al acabar Si hay varias llamadas simultáneas,](https://reader035.vdocumento.com/reader035/viewer/2022070909/5f8e023e38e3cb00e53e7fa1/html5/thumbnails/6.jpg)
22.12.2010
factorial recursivo
factorial (3) return 3 *
factorial (2) return 2 *
factorial (1) return 1 *
factorial (0) return 1
en cada llamada tenemos variables locales independientes
6
![Page 7: Fundamentos de Programaciónpepe/doc/fprg/07-recursion.ppt.pdf22.12.2010 argumentos y variables locales Se crean con la llamada Desaparecen al acabar Si hay varias llamadas simultáneas,](https://reader035.vdocumento.com/reader035/viewer/2022070909/5f8e023e38e3cb00e53e7fa1/html5/thumbnails/7.jpg)
factorial iterativo
¿Usa menos memoria? SÍ ¿Tarda menos? Hay que medirlo
22.12.2010
public int metodo2(int n) { int resultado = 1; for (int i = 1; i <= n; i++) resultado *= i; return resultado; }
7
![Page 8: Fundamentos de Programaciónpepe/doc/fprg/07-recursion.ppt.pdf22.12.2010 argumentos y variables locales Se crean con la llamada Desaparecen al acabar Si hay varias llamadas simultáneas,](https://reader035.vdocumento.com/reader035/viewer/2022070909/5f8e023e38e3cb00e53e7fa1/html5/thumbnails/8.jpg)
22.12.2010
¿recursión o iteración?
Son dos formas de conseguir que un programa haga muchas veces lo mismo con alguna variante
Toda iteración puede pasar a recursión todo bucle puede convertirse en un método que se
llama a sí mismo normalmente es fácil de programar
Toda recursión puede pasar a iteración todo método recursivo se puede escribir como bucle puede ser difícil de programar
8
![Page 9: Fundamentos de Programaciónpepe/doc/fprg/07-recursion.ppt.pdf22.12.2010 argumentos y variables locales Se crean con la llamada Desaparecen al acabar Si hay varias llamadas simultáneas,](https://reader035.vdocumento.com/reader035/viewer/2022070909/5f8e023e38e3cb00e53e7fa1/html5/thumbnails/9.jpg)
22.12.2010
iteración → recursión
while (p) { x; }
void metodo(...) { if (p) { x; metodo(...); } }
9
![Page 10: Fundamentos de Programaciónpepe/doc/fprg/07-recursion.ppt.pdf22.12.2010 argumentos y variables locales Se crean con la llamada Desaparecen al acabar Si hay varias llamadas simultáneas,](https://reader035.vdocumento.com/reader035/viewer/2022070909/5f8e023e38e3cb00e53e7fa1/html5/thumbnails/10.jpg)
22.12.2010
iteración → recursión Iterator<Gusano> itg = gusanos.iterator(); while (itg.hasNext()) { Gusano gusano = itg.next(); -- pinta -- }
void metodo(Iterator<Gusano> itg) { if (itg.hasNext()) { Gusano gusano = itg.next(); -- pinta -- metodo(itg); } } 10
![Page 11: Fundamentos de Programaciónpepe/doc/fprg/07-recursion.ppt.pdf22.12.2010 argumentos y variables locales Se crean con la llamada Desaparecen al acabar Si hay varias llamadas simultáneas,](https://reader035.vdocumento.com/reader035/viewer/2022070909/5f8e023e38e3cb00e53e7fa1/html5/thumbnails/11.jpg)
serie de fibonacci
Leonardo de Pisa, filius Bonaccio, (1202) 0 1 1 2 3 5 8 13 21 34 55 89 144 ... f(n) = f(n-1) + f(n-2)
f(0) = 0 f(1) = 1
22.12.2010 11
![Page 12: Fundamentos de Programaciónpepe/doc/fprg/07-recursion.ppt.pdf22.12.2010 argumentos y variables locales Se crean con la llamada Desaparecen al acabar Si hay varias llamadas simultáneas,](https://reader035.vdocumento.com/reader035/viewer/2022070909/5f8e023e38e3cb00e53e7fa1/html5/thumbnails/12.jpg)
método recursivo
22.12.2010
public int metodo1(int n) { if (n < 1) return 0; if (n == 1) return 1; return metodo1(n - 1) + metodo1(n - 2); }
12
![Page 13: Fundamentos de Programaciónpepe/doc/fprg/07-recursion.ppt.pdf22.12.2010 argumentos y variables locales Se crean con la llamada Desaparecen al acabar Si hay varias llamadas simultáneas,](https://reader035.vdocumento.com/reader035/viewer/2022070909/5f8e023e38e3cb00e53e7fa1/html5/thumbnails/13.jpg)
método iterativo
22.12.2010
public int metodo2(int n) { if (n < 1) return 0; int f0 = 0; int f1 = 1; for (int i = 2; i <= n; i++) { int fn = f0 + f1; f0 = f1; f1 = fn; } return f1; }
13
![Page 14: Fundamentos de Programaciónpepe/doc/fprg/07-recursion.ppt.pdf22.12.2010 argumentos y variables locales Se crean con la llamada Desaparecen al acabar Si hay varias llamadas simultáneas,](https://reader035.vdocumento.com/reader035/viewer/2022070909/5f8e023e38e3cb00e53e7fa1/html5/thumbnails/14.jpg)
recursivo con memoria
22.12.2010
private int[] serie = new int[100];
public Fibonacci() { for (int i = 0; i < serie.length; i++) serie[i] = -1; serie[0] = 0; serie[1] = 1; }
public int metodo3(int n) { if (serie[n] < 0) serie[n] = metodo3(n - 1) + metodo3(n - 2); return serie[n]; }
14
![Page 15: Fundamentos de Programaciónpepe/doc/fprg/07-recursion.ppt.pdf22.12.2010 argumentos y variables locales Se crean con la llamada Desaparecen al acabar Si hay varias llamadas simultáneas,](https://reader035.vdocumento.com/reader035/viewer/2022070909/5f8e023e38e3cb00e53e7fa1/html5/thumbnails/15.jpg)
ejercicio 1
fact(n) = 1 n < 2 n * fact (n-1) n > 1
22.12.2010 15
![Page 16: Fundamentos de Programaciónpepe/doc/fprg/07-recursion.ppt.pdf22.12.2010 argumentos y variables locales Se crean con la llamada Desaparecen al acabar Si hay varias llamadas simultáneas,](https://reader035.vdocumento.com/reader035/viewer/2022070909/5f8e023e38e3cb00e53e7fa1/html5/thumbnails/16.jpg)
ejercicio 2
A(m, n) = n+1 m = 0 A(m-1, n) m > 0 & n = 0 A(m-1, A(m, n-1)) m > 0 & n > 0
22.12.2010 16
![Page 17: Fundamentos de Programaciónpepe/doc/fprg/07-recursion.ppt.pdf22.12.2010 argumentos y variables locales Se crean con la llamada Desaparecen al acabar Si hay varias llamadas simultáneas,](https://reader035.vdocumento.com/reader035/viewer/2022070909/5f8e023e38e3cb00e53e7fa1/html5/thumbnails/17.jpg)
ejercicio 3
máximo común divisor recursivo e iterativo
mcd(a, b) = a a = b mcd(a-b, b a > b mcd(a, b-a) a < b
22.12.2010 17
![Page 18: Fundamentos de Programaciónpepe/doc/fprg/07-recursion.ppt.pdf22.12.2010 argumentos y variables locales Se crean con la llamada Desaparecen al acabar Si hay varias llamadas simultáneas,](https://reader035.vdocumento.com/reader035/viewer/2022070909/5f8e023e38e3cb00e53e7fa1/html5/thumbnails/18.jpg)
ejercicio 4.1
torres de hanoi hay que mover N discos de la torre A a la torre
B de forma que sólo se puede mover un disco cada vez nunca puede haber un disco de mayor tamaño sobre
otro de menor tamaño se puede usar una torre C auxiliar
22.12.2010 18
![Page 19: Fundamentos de Programaciónpepe/doc/fprg/07-recursion.ppt.pdf22.12.2010 argumentos y variables locales Se crean con la llamada Desaparecen al acabar Si hay varias llamadas simultáneas,](https://reader035.vdocumento.com/reader035/viewer/2022070909/5f8e023e38e3cb00e53e7fa1/html5/thumbnails/19.jpg)
ejercicio 4.2
solución
22.12.2010 19
![Page 20: Fundamentos de Programaciónpepe/doc/fprg/07-recursion.ppt.pdf22.12.2010 argumentos y variables locales Se crean con la llamada Desaparecen al acabar Si hay varias llamadas simultáneas,](https://reader035.vdocumento.com/reader035/viewer/2022070909/5f8e023e38e3cb00e53e7fa1/html5/thumbnails/20.jpg)
ejercicio 4.3
programar mueve(int n, int A, int B, int C)
si n = 1, se mueve 1 de A a B si n > 1
1. se mueven n-1 de A a C 2. se mueve 1 de A a B 3. se mueve 1 de C a B
22.12.2010 20
![Page 21: Fundamentos de Programaciónpepe/doc/fprg/07-recursion.ppt.pdf22.12.2010 argumentos y variables locales Se crean con la llamada Desaparecen al acabar Si hay varias llamadas simultáneas,](https://reader035.vdocumento.com/reader035/viewer/2022070909/5f8e023e38e3cb00e53e7fa1/html5/thumbnails/21.jpg)
ejercicio 5
recursivo e iterativo buscar un entero N en un array ordenado empezamos entre a= 0 y z=array.length si a < z: FALSE miramos en el medio m= (a+z)/2 si array[m] = N: TRUE si array[m] < N: busca entre m+1 y z si array[m] > N: busca entre a y m-1
22.12.2010 21
![Page 22: Fundamentos de Programaciónpepe/doc/fprg/07-recursion.ppt.pdf22.12.2010 argumentos y variables locales Se crean con la llamada Desaparecen al acabar Si hay varias llamadas simultáneas,](https://reader035.vdocumento.com/reader035/viewer/2022070909/5f8e023e38e3cb00e53e7fa1/html5/thumbnails/22.jpg)
ejercicio 6
dadas 2 listas ordenadas de String, combinarlas respetando el orden
List<String> merge(List<String>, List<String> b)
22.12.2010 22