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,
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).
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):