Anteriormente, apresentamos uma definição recursiva para o conjunto dos números naturais, N. Outra maneira de representar o conjunto N é 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 n in N, retorne uma lista de booleanos correspondente a sequência de bits que representa n em notação binária.

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:
  1. Caso Base: Se o número $ n $ for 0, retornamos uma lista vazia, já que não há bits para representar.
  2. Passo Recursivo: Dividimos $ n $ por 2. O resto dessa divisão nos dá o bit menos significativo (True para 1 e False 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:
binario(n) = binario(lfloor n2 rfloor) + [n mod 2 == 1]
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]

Exercícios relacionados