Como converter um número decimal em binário? (com recursividade) · rafaelmoraes003

Digamos que você queira saber qual é o equivalente do número 4 em binário.

Para transformar um decimal em binário, é necessário guardar o resto da divisão dele por 2 e ir dividindo o número enquanto ele for maior que 0.

Ficou confuso? Deixa que eu explico melhor:

O resto da divisão de 4 por 2 é 0, que representa um digito binário. Para descobrir os outros dígitos binários, é necessário continuar realizando divisões por 2.

Exemplificando, o esquema fica assim:

4 % 2 = 0     4 // 2 = 2 (agora, quem será dividido por 2 é o 2)
2 % 2 = 0     2 // 2 = 1 (agora, quem será dividido por 2 é o 1)
1 % 2 = 1     1 // 2 = 0 (agora, quem será dividido por 2 é o 0)
Quando n é <= 0, retorna-se 0

Se juntar todos os dígitos binário, o resultado fica 001 (o último 0 não entra aqui), mas 4 em binário é 100! Mas calma, o algoritmo não está errado, é só a ordem de organização dos dígitos que não está correta.

Recapitulando, temos:

0 ( 4 % 2 )
0 ( 2 % 2 )
1 ( 1 % 2 ) -> último dígito válido
0 ( 1 / 2 <= 0 )

A conta é feita a partir do último digito válido obtido, e é feita com o dígito somado de 10 vezes o seu antecessor

O último dígito é o 1, portanto: 1 + 10 * 0 (esse 0 é aquele que é retornado quando a divisão é menor ou igual a 0)

Esse cálculo resulta em: 1 (fique atento à ordem de precedência)

O próximo digito válido é o 0, portanto: 0 + 10 * 1 (esse 1 é resultado do cálculo de cima).

Esse cálculo resulta em: 10

O próximo digito válido é o 0, portanto: 0 + 10 * 10 (esse 10 é resultado do cálculo de cima).

Ao final, as operações resultam em 100, que é o equivalente binário do 4!

A representação desse esquema em forma de código pode ser representada da seguinte forma:

def decimal_to_binary(n):
    if n <= 0:
        return 0
    else:
        return n % 2 + 10 * (decimal_to_binary(n // 2))

Complementando...

Sei que a ideia é explicar o algoritmo e o conceito de recursão, mas tem um detalhe que não pode ser ignorado, principalmente ao se ensinar funções recursivas.

Cada vez que uma função é executada, a chamada é colocada na pilha - veja este artigo para mais informações, mas este gif em particular ilustra bem:

call stack

Com chamadas recursivas é a mesma coisa: cada vez que uma chamada é feita, ela fica empilhada, e só é desempilhada quando todas as subsequentes terminarem (a exceção é quando a linguagem otimiza recursão em cauda, mas não é o caso). E em todas as linguagens, existe um limite para o tamanho da pilha, e quando ele estoura, ocorre o famoso erro de "stack overflow" (estouro de pilha).

Como o seu código está em Python, vejamos o que acontece com um número grande:

def decimal_to_binary(n):
    if n <= 0:
        return 0
    else:
        return n % 2 + 10 * (decimal_to_binary(n // 2))

print(decimal_to_binary(2 ** 1000))

Neste caso ocorre o erro:

RecursionError: maximum recursion depth exceeded in comparison

Pois o tamanho máximo da pilha foi excedido. Até é possível aumentar o limite:

def decimal_to_binary(n):
    if n <= 0:
        return 0
    else:
        return n % 2 + 10 * (decimal_to_binary(n // 2))

import sys
sys.setrecursionlimit(2000)
print(decimal_to_binary(2 ** 1000)) # não dá mais erro

Mas na verdade, para este algoritmo, a solução iterativa me parece mais adequada:

def decimal_to_binary(n):
    result = expoente = 0
    while n > 0:
        n, digito = divmod(n, 2) # divide e pega o resto, tudo de uma vez
        result += (10 ** expoente) * digito
        expoente += 1
    return result

# não preciso aumentar o limite de recursão
print(decimal_to_binary(2 ** 1000))

Assim não preciso aumentar o limite máximo de recursão, pois só vai ter uma única chamada na pilha.

Não estou dizendo que recursão é "do mal" ou que nunca deva ser usada. É um conceito importante e tem muitos usos. Por exemplo, em árvores, muitos algoritmos podem ser melhores expressos de forma recursiva. Mas para o caso citado acima, a versão iterativa me parece mais adequada.

Mais alguns detalhes

Vale lembrar que na verdade estamos gerando um número cujos dígitos equivalem à representação binária. Por exemplo:

b = decimal_to_binary(21)
print(b) # 10101
print(type(b)) # <class 'int'>

O resultado é 10101, e veja que o tipo é int (ou seja, é um valor numérico). Então na verdade o valor de b é "dez mil cento e um". O que eu fiz na verdade foi gerar um número na base 10, cujos dígitos correspondem a 21 na base 2. Mas o valor dele é dez mil cento e um, então não adianta usá-lo achando que seu valor será equivalente a 21.

Claro que na hora de imprimir "não faz diferença visual", mas se for usar esse valor para algum cálculo, por exemplo, não vai funcionar da maneira esperada.

Por fim, se for para transformar o número em uma string contendo a representação binária deste, o próprio Python já disponibiliza várias formas nativas:

n = 21

# com f-string
print(f'{n:b}') # 10101

# ou format
print('{:b}'.format(n)) # 10101

# ou bin (mas ele coloca um prefixo para indicar que o valor está em binário)
print(bin(n)) # 0b10101
# se quiser retirar o prefixo
print(bin(n)[2:]) # 10101