domingo, 2 de septiembre de 2012

Recursividad - Ejercicios resueltos 0

Sin duda, la idea de recursividad es clara pero su implementación es lo más engorroso. Basta con leer "El Principito" de Antoine de Saint-Exupéry para reírnos con el diálogo recursivo del niño con el borracho (Capítulo XII).

Vamos a ir planteando algunos problemas y vamos a pasar por el planteamiento hasta llegar a la implementación.

1.- Confecciones un algoritmo que permita calcular la potencia de a elevado a n, según se aprecia en los siguientes cálculos.
a) exponente par:
$$5^8 = 5^4 \times 5^4 \\ 5^4 = 5^2 \times 5^2 \\ 5^2 = 5 \times 5\\$$

b) exponente impar: $$5^7 = 5^3 \times 5^3 \times 5\\ 5^3 = 5 \times 5 \times 5 \\ $$ Como vemos en la gráfica tenemos la condición de paro (borde) en el fondo de la secuencia: "Si el exponente es 1 retorne la base".
Ahora que tenemos el borde tenemos que fijarnos en el resto del problema.

Si nos fijamos bien, en el caso del exponente par se debe dividir la potencia en la multiplicación de la base elevada a la mitad del exponente original. A su vez, si el exponente es mayor a 1, se debe repetir esta tarea (se crea una especie de árbol).

Para el caso de los exponentes impares, se separa la expreción en las base sola (elevada a 1 en realidad) por la base elevada al exponente menos 1 dividido por la mitad (fácil de intuir, difícil de explicar).

La implementación en Java es la siguiente:

public static int elevado(int a, int n){

 //Si el exponente es 1 retorna la base.
 if (n==1) return a;

 //Si el exponente es par retorna la multiplicación
 //de la base elevado a la mitad del exponente
 //consigo misma.
 if (n%2==0) return (elevado(a,n/2) * elevado(a,n/2));

 //Si el exponenete es impar retorna la base multiplicada
 // por la base elevada a la mitad del exponente -1 por la
 //base elevada al exponenete menos uno.
 else return (elevado(a,(n-1)/2) * elevado(a,(n-1)/2) * a);
}

No hay comentarios:

Publicar un comentario