fundamentos de programaciónpepe/doc/fprg/07-recursion.ppt.pdf22.12.2010 argumentos y variables...

22
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

Upload: others

Post on 03-Aug-2020

6 views

Category:

Documents


0 download

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,

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,

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,

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,

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,

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,

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,

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,

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,

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,

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,

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,

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,

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,

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,

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,

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,

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,

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,

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,

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,

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,

ejercicio 6

 dadas 2 listas ordenadas de String, combinarlas respetando el orden

  List<String> merge(List<String>, List<String> b)

22.12.2010 22