Anteriormente, apresentamos uma definição recursiva para o conjunto dos números naturais,
. Outra maneira de representar o conjunto
é utilizando sequências finitas (listas) de bits. Tal representação consiste na conversão de números de base 10 para base 2 e vice-versa.
Apresente uma função recursiva que, a partir de um número natural
, retorne uma lista de booleanos correspondente a sequência de bits que representa
em notação binária.
Apresente uma função recursiva que, a partir de um número natural
Passo 1
Beleza, vamos lá! O exercício pede para a gente criar uma função recursiva que, dado um número natural $ n $, transforme esse número na sua representação binária em forma de lista de booleanos. Ou seja, cada elemento da lista será
True
ou False
, representando os bits do número. Para resolver isso, vamos precisar entender sobre recursão e sistema binário.Passo 2
Primeiro, vamos lembrar como funciona a conversão de um número decimal para binário. Em termos simples, isso envolve dividir o número por 2 e anotar o resto, repetindo esse processo com o quociente até que ele seja zero. Cada resto representa um bit na posição correspondente.
Passo 3
Agora, pensando de forma recursiva, podemos definir a função da seguinte maneira:
- Caso Base: Se o número $ n $ for 0, retornamos uma lista vazia, já que não há bits para representar.
- Passo Recursivo: Dividimos $ n $ por 2. O resto dessa divisão nos dá o bit menos significativo (
True
para 1 eFalse
para 0). Chamamos a função novamente com o quociente da divisão para obter os bits mais significativos e adicionamos o bit atual à lista.
Passo 4
Vamos detalhar o passo recursivo com uma fórmula:
Aqui,
n mod 2 == 1
verifica se o resto da divisão por 2 é 1 (True
) ou 0 (False
).Passo 5
Agora, juntando tudo e escrevendo a função, podemos ter algo assim em pseudocódigo:
def binario(n):
if n == 0:
return []
else:
return binario(n // 2) + [n % 2 == 1]
Resposta
A função recursiva para converter um número natural $ n $ em uma lista de booleanos representando sua sequência de bits é:
def binario(n):
if n == 0:
return []
else:
return binario(n // 2) + [n % 2 == 1]