Escreva uma função recursiva que recebe um número
como parâmetro e devolve a quantidade de dígitos 1 presentes na representação binária de
. Por exemplo, para
, a função deve devolver 2 que é a quantidade de dígitos 1’s na representação binária de
.
Passo 1
O que o enunciado pede e o que é dado:
- Pede-se uma função recursiva que recebe um número inteiro
como parâmetro e devolve a quantidade de dígitos presentes na representação binária de . - Exemplo dado: para
a função deve devolver porque em binário é e há dois dígitos . - Entende-se que
é um inteiro não negativo (ou seja, ). Não há figura nem tabela no enunciado.
Passo 2
Ideia matemática por trás da solução (como pensar o problema na prova):
- A representação binária de um número
é formada pelos restos da divisão sucessiva por . O último bit (bit menos significativo) é e os bits restantes correspondem aos bits de . - Isso nos dá uma relação natural de recursão para a contagem de uns:
Aqui
é a quantidade de dígitos
em
escrito em binário;
vale
se o último bit de
for
(quando
é ímpar) e
caso contrário (quando
é par).
- Em palavras: conte se o último bit é
e some isso à contagem de s no número obtido ao dividir por (desprezando resto).
Passo 3
Justificativa de validade e condição de parada (importante na prova):
- Condição de parada: quando
não há bits , logo . Isso impede recursão infinita. - Cada chamada recursiva reduz
para , que é estritamente menor que para . Assim a recursão termina em número finito de passos (aproximadamente chamadas). - Correção: a fórmula do passo anterior corresponde exatamente ao procedimento de retirar o bit menos significativo e contar se ele é
.
Passo 4
Construção passo a passo da função recursiva (pseudo-código e explicação linha a linha):
- Escrever a assinatura: a função recebe
e devolve um inteiro. - Testar a condição base: se
retornar . - Caso contrário:
- Calcular o último bit:
. - Chamar recursivamente a função com
. - Somar os dois resultados e retornar.
- Calcular o último bit:
Pseudo-código (linguagem muito parecida com Python, linha a linha):
- Definir função com nome intuitivo, por exemplo
count_ones(n). - Se
n == 0: retornar0. - Senão: retornar
(n % 2) + count_ones(n // 2).
Passo 5
Implementação em Python (explicando por que cada peça corresponde à ideia):
n % 2calcula, que é se é ímpar e se é par. n // 2calcula, reduzindo o problema para um número com um bit a menos. - A chamada recursiva
count_ones(n // 2)aplica exatamente a mesma regra ao subproblema menor.
Passo 6
Exemplo concreto, avaliando passo a passo para
:
- Começa-se com
. Como , aplica-se a regra: -
(último bit é ). - Novo
para a recursão: . - Então
.
-
- Para
: -
. -
. -
.
-
- Para
: -
. -
. -
.
-
- Para
: (caso base). - Substituindo para cima:
-
. -
. -
.
-
- Resultado:
, como esperado.
Passo 7
Complexidade e observações práticas para a prova:
- Número de chamadas recursivas ~
, então complexidade de tempo é . - Complexidade de espaço (pilha de chamadas) também é
. - Se o enunciado proibir recursão profunda por limite de pilha, pode-se transformar facilmente em versão iterativa, mas aqui o pedido foi recursivo, então usamos a recursão direta.
- Dica para a prova: escreva primeiro a relação de recursão
e o caso base . Depois traduza para código.
Resposta
def count_ones(n):
if n == 0:
return 0
return (n % 2) + count_ones(n // 2)
if n == 0:
return 0
return (n % 2) + count_ones(n // 2)