Escreva uma função recursiva que recebe um número n como parâmetro e devolve a quantidade de dígitos 1 presentes na representação binária de n. Por exemplo, para n=5, a função deve devolver 2 que é a quantidade de dígitos 1’s na representação binária de 5\left(101_{2}\right).

Passo 1

O que o enunciado pede e o que é dado:
  • Pede-se uma função recursiva que recebe um número inteiro n como parâmetro e devolve a quantidade de dígitos 1 presentes na representação binária de n.
  • Exemplo dado: para n=5 a função deve devolver 2 porque 5 em binário é 101_{2} e há dois dígitos 1.
  • Entende-se que n é um inteiro não negativo (ou seja, n\ge0). 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 n é formada pelos restos da divisão sucessiva por 2. O último bit (bit menos significativo) é n \bmod 2 e os bits restantes correspondem aos bits de \left\lfloor\dfrac{n}{2}\right\rfloor.
  • Isso nos dá uma relação natural de recursão para a contagem de uns: f(0)=0,
f(n)=f\!\left(\left\lfloor\dfrac{n}{2}\right\rfloor\right)+\bigl(n\bmod 2\bigr)\quad\text{para }n\ge1.
Aqui f(n) é a quantidade de dígitos 1 em n escrito em binário; \bigl(n\bmod 2\bigr) vale 1 se o último bit de n for 1 (quando n é ímpar) e 0 caso contrário (quando n é par).
  • Em palavras: conte se o último bit é 1 e some isso à contagem de 1s no número obtido ao dividir n por 2 (desprezando resto).

Passo 3

Justificativa de validade e condição de parada (importante na prova):
  • Condição de parada: quando n=0 não há bits 1, logo f(0)=0. Isso impede recursão infinita.
  • Cada chamada recursiva reduz n para \left\lfloor\dfrac{n}{2}\right\rfloor, que é estritamente menor que n para n\ge1. Assim a recursão termina em número finito de passos (aproximadamente \lfloor\log_2 n\rfloor+1 chamadas).
  • Correção: a fórmula do passo anterior corresponde exatamente ao procedimento de retirar o bit menos significativo e contar se ele é 1.

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 n e devolve um inteiro.
  • Testar a condição base: se n=0 retornar 0.
  • Caso contrário:
    • Calcular o último bit: \bigl(n\bmod 2\bigr).
    • Chamar recursivamente a função com \left\lfloor\dfrac{n}{2}\right\rfloor.
    • Somar os dois resultados e retornar.
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: retornar 0.
  • Senão: retornar (n % 2) + count_ones(n // 2).

Passo 5

Implementação em Python (explicando por que cada peça corresponde à ideia):
  • n % 2 calcula \bigl(n\bmod 2\bigr), que é 1 se n é ímpar e 0 se n é par.
  • n // 2 calcula \left\lfloor\dfrac{n}{2}\right\rfloor, 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 \,n=5:
  • Começa-se com n=5. Como 5\ne0, aplica-se a regra:
    • 5\bmod 2=1 (último bit é 1).
    • Novo n para a recursão: \left\lfloor\dfrac{5}{2}\right\rfloor=2.
    • Então f(5)=1+f(2).
  • Para n=2:
    • 2\bmod 2=0.
    • \left\lfloor\dfrac{2}{2}\right\rfloor=1.
    • f(2)=0+f(1).
  • Para n=1:
    • 1\bmod 2=1.
    • \left\lfloor\dfrac{1}{2}\right\rfloor=0.
    • f(1)=1+f(0).
  • Para n=0: f(0)=0 (caso base).
  • Substituindo para cima:
    • f(1)=1+0=1.
    • f(2)=0+1=1.
    • f(5)=1+1=2.
  • Resultado: f(5)=2, como esperado.

Passo 7

Complexidade e observações práticas para a prova:
  • Número de chamadas recursivas ~ \lfloor\log_2 n\rfloor+1, então complexidade de tempo é O(\log n).
  • Complexidade de espaço (pilha de chamadas) também é O(\log n).
  • 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 \;f(n)=f\!\left(\left\lfloor\dfrac{n}{2}\right\rfloor\right)+(n\bmod 2)\; e o caso base f(0)=0. Depois traduza para código.

Resposta

def count_ones(n):
if n == 0:
return 0
return (n % 2) + count_ones(n // 2)

Exercícios relacionados