Conversão de decimal para binário usando Indução

Novamente a abordagem é indutiva. O algoritmo implementará o método clássico e simples de conversão.
Idéa indutiva:

• Caso base: Se o valor que será convertido for igual a 0 ou 1, então o problema está automaticamente resolvido.
• Hipótese de indução: Nós podemos assumir que já temos os n - 1 bits que compõem a representação binária. Pode até parecer uma suposição absurda, mas é dessa forma que a indução trabalha =D.
• Caso geral: Agora basta estender a solução adicionando o último bit ao final da resposta que a hipótese de indução nos deu. E assim como acontece na prova de um teorema, a utilização da hipótese de indução no passo indutivo é obrigatória.

A seguir, apresentamos algumas implementações que seguem "exatamente" a idéia mostrada acima. Notem a presença do caso base e da hipótese de indução "dec2bin(n / 2)" em todas elas.

• Implementação em Haskell 

dec2bin :: Int -> String
dec2bin 0 = "0"
dec2bin 1 = "1"
dec2bin n = dec2bin(n `div` 2) ++ show(n `mod` 2)

• Implementação em Python

def dec2bin(n):
  if n < 2:
    print (n),
  else:
    dec2bin(n / 2)
    print (n % 2),

• Implementação em Java

public static void dec2bin(int n) {
    if (n < 2) {
        System.out.println(n);
    } else {
        dec2bin(n / 2);
        System.out.println(n % 2);
    }
}

• Implementação em JavaScript

function dec2bin(a)
{
   if(a < 2)
     return a;
   else
     return dec2bin(Math.floor(a / 2)) + “” + (a % 2);
}

• Implementação em C++

void dec2bin(int n){
   if(n < 2)
      cout << n;
   else {
      dec2bin(n / 2);
      cout << (n % 2);
   }
}

O tempo de execução do algoritmo apresentado aqui é expresso pela relação de recorrência T(n) = T(n/2) + 1.
Fazendo n = $2^k$, temos

$T(n) = T(2^{k-1}) + 1$

$T(n) = T(2^{k-2}) + 1 + 1$

$T(n) = T(2^{k-3}) + 1 + 1 + 1$

$T(n) = T(2^{k-4}) + 1 + 1 + 1 + 1$

....

$T(n) = T(2^0) + 1 + 1 + 1 + 1 + 1 + 1 +  ...  + 1 + 1$

$T(n) = k$

Como $n = 2^k$, temos que $log  n = log  2^k$ e $log  n = k$, então a complexidade do método é limitada assintoticamente pela função logarítmica. Ou seja, $T(n) = O(log  n)$.