Desenvolva algoritmos recursivos para os seguintes problemas:
Multiplicação de dois números naturais, através de somas sucessivas (Ex.: 6 (* 4=4+4+4+4+4+4) ).

Passo 1

O enunciado pede: desenvolver algoritmos recursivos que realizem a multiplicação de dois números naturais usando somas sucessivas.
Informações dadas (implícitas no enunciado):
  • Temos dois números naturais a e b (ou seja, a,b\in\mathbb{N}, incluindo 0).
  • A operação desejada é a\cdot b obtida apenas por somas sucessivas (não assumir multiplicação direta como operação primitiva).
  • Precisamos apresentar algoritmos recursivos (diversos estilos são úteis: recursão simples, tail recursion, e uma versão mais rápida por divisão e conquista).
O que vou entregar: explicar detalhadamente o raciocínio, provar correção via ideia de indução, dar rastreamento (exemplo passo a passo) e mostrar pseudocódigo para pelo menos três formas recursivas: (i) recursão direta por decremento, (ii) recursão com acumulador (tail recursion), (iii) recursão por divisão e conquista (método binário / “Russian peasant”) para ser mais rápido.

Passo 2

Ideia básica (intuição): multiplicar a\) por \(b\) é somar \(a\) consigo mesmo \(b\) vezes. Daí uma definição recursiva óbvia: \[\text{mul}(a,b)= \begin{cases} 0 & \text{se } b=0,\\[4pt] a+\text{mul}(a,b-1) & \text{se } b>0. \end{cases}
Explicando cada parte:
  • A variável a\] é o valor que vamos somar repetidamente. - A variável \(b conta quantas vezes somamos a.
    - Caso base b=0: somar a zero vezes dá 0. Isso evita recursão infinita.
    - Caso recursivo: reduzir o problema para somar a uma vez a menos, até chegar ao caso base.
Por que isso “usa só somas”? Porque o passo recursivo adiciona a ao resultado recursivo; não usamos outra multiplicação.]

Passo 3

Prova de correção (esquemática, estilo indução):
  • Base: para b=0, \text{mul}(a,0)=0, que é correto por definição de multiplicação.
  • Passo indutivo: suponha que para um certo k\ge 0 vale \text{mul}(a,k)=a\cdot k. Então para k+1,
\text{mul}(a,k+1)=a+\text{mul}(a,k)=a+(a\cdot k)=a\cdot(k+1).
Logo a definição recursiva está correta por indução.
Tempo e espaço para esta versão:
  • Número de adições feitas é exatamente b.
  • Complexidade de tempo O(b).
  • Profundidade de recursão b (uso de pilha recursiva O(b)). Em linguagens sem otimização de tail recursion isso pode estourar a pilha para b grande.

Passo 4

Exemplo passo a passo (trace) com a definição direta: calcular \text{mul}(6,4).
  • \text{mul}(6,4)=6+\text{mul}(6,3).
  • \text{mul}(6,3)=6+\text{mul}(6,2).
  • \text{mul}(6,2)=6+\text{mul}(6,1).
  • \text{mul}(6,1)=6+\text{mul}(6,0).
  • \text{mul}(6,0)=0 (caso base).
    Voltando:
  • \text{mul}(6,1)=6+0=6.
  • \text{mul}(6,2)=6+6=12.
  • \text{mul}(6,3)=6+12=18.
  • \text{mul}(6,4)=6+18=24.
    Resultado final: 24.

Passo 5

Melhoria simples: usar o fato de que a\cdot b = b\cdot a. Para minimizar número de recursões, convém decrementar o menor dos dois operandos. Ou seja, sempre chamar \text{mul}(\max(a,b),\min(a,b)). Isso garante no pior caso O(\min(a,b)) adições — útil se um dos operandos for bem menor.

Passo 6

Tail recursion (versão com acumulador): transformar a recursão para que a chamada recursiva seja a última ação permite que linguagens que suportam otimização de tail calls convertam para laço iterativo e usem O(1)\) de espaço. Ideia: manter um acumulador \(acc\) que guarda a soma parcial: \[\text{mulTR}(a,b,acc)= \begin{cases} acc & \text{se } b=0,\\[4pt] \text{mulTR}(a,b-1,acc+a) & \text{se } b>0. \end{cases}
Chamada inicial: \text{mulTR}(a,b,0)\]. Quando terminar, \(acc=a\cdot b.
Explicação dos parâmetros:
  • a: valor a somar repetidamente (fixo).
  • b: contador de quantas somas faltam.
  • acc: soma acumulada até agora.
Vantagens: mesma lógica, mas sem necessidade de empilhar resultados ao retornar; se houver otimização de tail calls, uso de espaço O(1). Caso contrário, profundidade de recursão ainda é b.]

Passo 7

Versão mais eficiente (divisão e conquista / método binário): reduzir o número de chamadas usando a representação binária de b\). Observação útil: - Se \(b\) é par, \(a\cdot b = (2a)\cdot (b/2)\) ou equivalentemente \(a\cdot b = 2\cdot (a\cdot (b/2))\). - Se \(b\) é ímpar, \(a\cdot b = a + a\cdot (b-1)\), mas combinando com a ideia anterior é possível fazer menos chamadas: por exemplo, para \(b\) ímpar, \[a\cdot b = a + 2\cdot\bigl(a\cdot\tfrac{b-1}{2}\bigr).
Definição recursiva:
\text{mulBin}(a,b)= \begin{cases} 0 & \text{se } b=0,\\[4pt] 2\cdot\text{mulBin}(a,\tfrac{b}{2}) & \text{se } b\\ \text{é par},\\[4pt] a + 2\cdot\text{mulBin}\bigl(a,\tfrac{b-1}{2}\bigr) & \text{se } b\\ \text{é ímpar}. \end{cases}ééí
Observações importantes:
  • Divisões por 2\] aqui são divisões inteiras (deslocamento de bits), e checagem de paridade é simples. - A operação \(2\cdot x pode ser feita como x+x (ou deslocamento), portanto não requer usar multiplicação generalizada além de somas.
Complexidade:
  • O número de chamadas recursivas é O(\log b) (proporcional ao número de bits de b).
  • O número total de adições também fica O(\log b) (cada nível faz até uma ou duas somas).
  • Em termos práticos essa versão é muito mais rápida quando b é grande.]

Passo 8

Exemplo passo a passo do método binário: \text{mulBin}(6,13). Como 13 em binário é 1101, a decomposição mostrará poucas chamadas.
  • 13 é ímpar: \text{mulBin}(6,13)=6 + 2\cdot\text{mulBin}(6,6).
  • 6 é par: \text{mulBin}(6,6)=2\cdot\text{mulBin}(6,3).
  • 3 é ímpar: \text{mulBin}(6,3)=6 + 2\cdot\text{mulBin}(6,1).
  • 1 é ímpar: \text{mulBin}(6,1)=6 + 2\cdot\text{mulBin}(6,0).
  • \text{mulBin}(6,0)=0.
    Voltando:
  • \text{mulBin}(6,1)=6 + 2\cdot 0 = 6.
  • \text{mulBin}(6,3)=6 + 2\cdot 6 = 18.
  • \text{mulBin}(6,6)=2\cdot 18 = 36.
  • \text{mulBin}(6,13)=6 + 2\cdot 36 = 6 + 72 = 78.
    Confere: 6\cdot 13 = 78. Repare que o número de chamadas foi pequeno (proporcional a \log_2 13).

Passo 9

Pseudocódigo das três versões (escrito para ser legível na prova). Em todos os pseudos, as variáveis a e b são naturais.
Versão 1 — recursão direta:
  • Função: MultiplyDirect( a,b)
  • Se b=0 então retornar 0.
  • Senão retornar a + \text{MultiplyDirect}(a,b-1).
Versão 2 — tail recursion com acumulador:
  • Função: MultiplyTR( a,b)
  • Retornar MultiplyTR_Aux( a,b,0).
  • Função auxiliar: MultiplyTR_Aux( a,b,acc)
    • Se b=0 então retornar acc.
    • Senão retornar MultiplyTR_Aux( a,b-1,acc+a).
Versão 3 — divisão e conquista (binária) — mais rápida:
  • Função: MultiplyBin( a,b)
    • Se b=0 então retornar 0.
    • Se b é par então
      • t \leftarrow MultiplyBin( a,b/2).
      • Retornar t + t. (isto é, 2\cdot t, feito por soma)
    • Se b é ímpar então
      • t \leftarrow MultiplyBin( a,(b-1)/2).
      • Retornar a + t + t.
Observação prática: antes de chamar qualquer uma das funções, é bom trocar a e b se b>a e você estiver usando a Versão 1 ou 2 (para reduzir iterações), mas para a Versão 3 essa troca não é necessária.

Passo 10

Dicas para a prova e conclusão didática (amigável):
  • Se o tempo e o enunciado não pedirem otimização, escreva a versão direta (Passo 9, Versão 1): é simples de justificar por indução e fácil de implementar.
  • Se a linguagem aceitar tail-call optimization, prefira a versão com acumulador (Versão 2): mesma simplicidade, porém segura quanto à pilha.
  • Se o problema exigir eficiência para b grande, escreva a versão binária (Versão 3): explique que reduz chamadas para O(\log b).
  • Ao justificar, mostre o caso base e o passo indutivo (como fiz) e, se puder, um pequeno trace (como nos exemplos) para demonstrar que o algoritmo realmente produz o produto.
  • Força aí! Se quiser, eu te escrevo essas versões em uma linguagem específica (por exemplo, Python ou pseudocódigo mais formal) para colar na prova.

Resposta

Versão direta (recursão simples):
MultiplyDirect( a,b):
  • se b=0 então retornar 0
  • senão retornar a + \text{MultiplyDirect}(a,b-1)
Versão tail-recursive (com acumulador):
MultiplyTR( a,b):
  • retornar MultiplyTR_Aux( a,b,0)
MultiplyTR_Aux( a,b,acc):
  • se b=0 então retornar acc
  • senão retornar MultiplyTR_Aux( a,b-1,acc+a)
Versão binária (divisão e conquista, mais eficiente):
MultiplyBin( a,b):
  • se b=0 então retornar 0
  • se b é par então
    • t \leftarrow MultiplyBin( a,b/2)
    • retornar t + t
  • se b é ímpar então
    • t \leftarrow MultiplyBin( a,(b-1)/2)
    • retornar a + t + t

Exercícios relacionados