trab

Recursión

Carlos Delgado Kloos
Ingeniería Telemática
Univ. Carlos III de Madrid
cdk@it.uc3m.es

Java: Recursión /

1

Método recursivo
Un método recursivo es aquel que
(directa oindirectamente)
se llama a si mismo.
(Para que el método recursivo defina
una computación que termina)
la(s) llamada(s) recursiva(s)
han de ser más sencilla(s)
(de acuerdo con alguna métrica)cdk@it.uc3m.es

Java: Recursión /

2

Ejemplo 1
public static long s (int n)
{if (n==1)
return 1;
else
return s(n-1)+n;
}

cdk@it.uc3m.es

Java: Recursión /

3

Ejemplo 1
s(3) =
s(2)+3=
(s(1)+2)+3 =
(1+2)+3 =
(3+3)=
6

cdk@it.uc3m.es

(llamada recursiva)
(llamada recursiva)
(llamada recursiva)
(suma)
(suma)

Java: Recursión /

4

Ejemplo 2
public static long s(int n)
{if (n==1)
return 1;
else
return s(n+1)+n;
}

cdk@it.uc3m.es

(para n>1)

Java: Recursión /

5

Ejemplo 2
s(3) =
(llam. rec.)
s(4)+3 =
(llam. rec.)
(s(5)+4)+3 =
(llam.rec.)
((s(6)+5)+4)+3 =
(llam. rec.)
(((s(7)+6)+5)+4)+3 =
(llam. rec.)
((((s(8)+7)+6)+5)+4)+3 =
...

No termina
cdk@it.uc3m.es

Java: Recursión /

6

¿Qué debe tener
un método recursivo?Condicional
Caso base (no recursivo)
Caso recursivo
(que se aproxima hacia
la condición del caso base)

cdk@it.uc3m.es

1
s(n-1)+n
(n==1)

Java: Recursión /

7

Ejercicios:cuentaAtras
void cuentaAtras (int contador)
{if(contador == 0)
return;
else {
System.out.println(""+contador);
cuentaAtras(--contador);
return;
}
}
cdk@it.uc3m.es

Java: Recursión /

8Ejercicio: cuadrado
(N-1)2 = N2 - 2N + 1
N2 = (N-1)2 + 2N - 1
cuadrado(1) = 1
cuadrado(N) = cuadrado(N-1) + 2N -1

cdk@it.uc3m.es

Java: Recursión /

9

Ejercicio: cuadrado
int cuadrado (int n){if (n == 0)
return 0;
else
return cuadrado(n-1)+2*n-1;
}

cdk@it.uc3m.es

Java: Recursión /

10

Ejercicio: misterio
misterio(0,Q) = Q
misterio(P,Q) = misterio(P-1, Q+1)
¿Cuánto...