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

Fundamentos de Programación

Métodos métodos recursivos

José A. Mañas <jmanas@dit.upm.es> Dpto. de Ingeniería de Sistemas Telemáticos

http://www.lab.dit.upm.es/~fprg/ 22.12.2010

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

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

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

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

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

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

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

22.12.2010

iteración → recursión

while (p) { x; }

void metodo(...) { if (p) { x; metodo(...); } }

9

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

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

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

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

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

ejercicio 1

 fact(n) = 1 n < 2 n * fact (n-1) n > 1

22.12.2010 15

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

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

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

ejercicio 4.2

 solución

22.12.2010 19

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

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

ejercicio 6

 dadas 2 listas ordenadas de String, combinarlas respetando el orden

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

22.12.2010 22