Exponenciação: Descrição indutiva e implementação em Java

Neste post, vamos descrever indutivamente um algoritmo que realiza a exponenciação. Em seguida, apresentaremos uma implementação em Java. Matematicamente, para calcular a exponencial $a^n$, fazemos:

                                                                   $\underbrace{a * a * a * ... * a * a}_\text{n termos} = a^n$

Descrição indutiva:

• Caso Base: Para n = 0, temos que $a^0 = 1$.
• Hipótese de Indução: Vamos assumir que a hipótese de indução sabe como calcular $a^{n-1}$.
• Caso Geral: Trivial, basta pegar a resposta que a hipótese de indução nos deu e multiplicar por a. E assim teremos:                                                                   $\underbrace{\overbrace{(a^{n-1})}^\text{Hipótese de Indução}*a}_\text{Caso Geral} = a^n$.

A implementação em Java segue exatamente a descrição indutiva apresentada acima.

• Implementação em Java

public class Potenciacao {
  public static int slowExp(int a, int n) {
    if (n == 0)
      return 1;
    else
      return slowExp(a, n - 1) * a;
  }

  public static void main(String[] args) {
    System.out.println(slowExp(2, 3));
  }
}

Complexidade
A implementação acima possui complexidade linear. Ou seja, T(n) = T(n-1) + O(1),onde n é o expoente da potência. Podemos fazer melhor?

@inductioncode