Conversão decimal -> binário com recursão

[Gabriela Cavalcante]

Olá! Estou com um código que "faz" a conversão de um número decimal para binário, mas ele acaba engolindo o último número que é para ser gerado... O código é o seguinte:

#include <iostream> 

using namespace std;

int bin(int k, int r) {    
  if (k == 0) return (10 * r);
  else return bin((k/2), (k%2) + (10 * r));
} 

int main() {  
	cout << bin(12, 0) << endl; 
} 

O problema é que se eu passo 12, ele mostrar 110, mas o correto seria 1100. Alguém poderia me sugerir algo?

Editado Agosto 8, 2014 por Gabriela Cavalcante

[ScreenBlack]

1) Quando uma recursividade necessitar de "else", a chance é muito grande de que esteja errada.

2) Como a recursividade necessita apenas de divisão, tendo como exceção o valor de sobra que não pode ser dividido, este será o momento para finalizar a recursão.

int bin(int k)
{
    if ( k < 2 ) // Momento de parada
        return k;
 
    return ( 10 * bin( k / 2 ) ) + k % 2; // Iniciando a multiplicação pelo valor que não pode mais ser dividido por 2 e somando com a sobra da divisão.
}
 
Chamada:
cout << bin(12) << endl;

PS: Vale lembrar que, se estiver utilizando um compilador 32 bits, o valor máximo em binário são 32 casas binárias (Dããã pra mim!! :P ). Mas acredito que vale a atenção, caso queira fazer testes com números grandes, pois é um detalhe que costuma passar batido.

Att.

Editado Agosto 8, 2014 por ScreenBlack

[Gabriela Cavalcante]

Obrigada pela explicação, mas então... antes eu fiz algo parecido com isso, meu else tinha ficado: else return ((k%2) + 10 * (bin(k/2)));

Só que agora eu queria pegar o que eu fiz e usar recursão de cauda, porque ai não é precisaria guardar a posição onde foi feita a chamada... tipo:

int fatorial(int num) 
 { 
 if (num == 1) 
 return num; 
 else 
 return num * fatorial(num - 1); 
}

Essa é a recursão sem cauda, e com cauda ficaria:

int fatorial_aux(int num, int parcial) 
{ 
 if (num == 1) 
 return parcial; 
 else 
 return fatorial_aux((num - 1), (parcial * num)); 
} 
 
int fatorial_cauda(int num) 
{ 
 return fatorial_aux(num, 1); 
} 

Por isso tentei fazer (como tá no código que postei inicialmente) o return como "else return bin((k/2), (k%2) + (10 * r));".

Caso minha explicação tenha fica confusa, posso tentar explicar melhor o que pretendia fazer com o código. Mas já te agradeço pela ajuda :)

[ScreenBlack]

Entendi.

No caso de recursão para conversão de decimal para binário, acredito que não seja possível fazer na forma de cauda, porque precisa da sequência inversa para poder gerar os valores na ordem correta.

Diferente do fatorial, onde tanto faz executar a multiplicação de frente para trás (que é o caso da recursão de cauda) ou de trás para frente.

Mesmo utilizando a recursão de cauda, não é aconselhável utilizar o "else", pois desestrutura a função por não existir um retorno geral definido. ^_^

int fatorial_aux(int num, int parcial)
{
    if (num == 1)
        return parcial;
 
    return fatorial_aux( (num - 1), (parcial * num) );
}

EDIT: Depois de tanto quebrar cabeça com teste de mesa, consegui fazer a recursão de cauda para conversão de número binário. :D

int binario_aux(int num, unsigned int parcial, int controle)
{
    if ( num < 2 )
        return pow(10, ++controle) + parcial;
 
    return binario_aux( (num / 2), ( pow(10, controle) * (num % 2) ) + parcial, ++controle );
}
 
int binario_cauda(int num)
{
    return binario_aux(num, 0, -1);
}

PS: Valor máximo em decimal permitido para a conversão no código que postei acima, é 1023. Isso é devido a utilização da função que calcula exponenciação, que retorna o valor no tipo "double" (float). Como o valor em binário ocupa mais casas do que em decimal, o tipo float acaba estourando.

Editado Agosto 8, 2014 por ScreenBlack

[Gabriela Cavalcante]

Caramba, obrigada! Vou estudar o código direitinho, para que em situações futuras eu o consiga fazer sem problema. Muito obrigada, pude entender melhor até a recursão com calda depois da sua explicação! Muito obrigada mesmo!