Para resolver el problema del algoritmo recursivo de la potencia se tiene que tener en cuenta ciertos puntos:

Planteando la fórmula

Sabemos que una base a la potencia n es igual a la base multiplicado por sí mismo n veces.

Por ejemplo

43 = 4 * 4 * 4.

Por lo tanto, podemos decir que nuestra fórmula es

Potencia (base, n) = base*base*base*base*base..... n veces

Teniendo en cuenta la base y el exponente que se requiere, planearemos los casos que se nos pueden presentar en el algoritmo.

Planteando el caso de forma recursiva

El caso base:

Sabemos que cualquier número a la potencia cero es igual a 1 (caso base 1)
Y que cualquier número a la potencia uno es igual a sí mismo (caso base 2)

A continuación el algoritmo para calcular la potencia de forma recursiva realizado en java:

double Potencia(double base,int exp){
 if(exp == 0){       
    return 1;
 }else{
    if(exp == 1){    
       return base;
    }else{
        return base * Potencia(base,exp-1) ;
    }
 }
}