Considere a função calc indicada abaixo:
a) Escreva a função calc de forma iterativa.
b) Escreva a função calc de forma recursiva.
b) Escreva a função calc de forma recursiva.
Passo 1
O enunciado dá a função
e pede duas coisas:
a) escrever de forma iterativa;
b) escrever de forma recursiva.
a) escrever
b) escrever
Informações importantes fornecidas pelo enunciado:
- A soma é indexada por
de até . - Cada termo da soma é
. - Queremos duas formas de implementação (iterativa e recursiva) que computem esse somatório.
Observação imediata: para evitar ambiguidade, vou interpretar a expressão como
ou seja, estamos somando, para cada
, o valor
.
Passo 2
Vamos entender a soma termo a termo. A soma é a soma de dois componentes:
Explicando cada parte:
-
é quatro vezes a soma dos inteiros de a . -
é simplesmente somado vezes (porque incluímos o ).
Vou agora usar fórmulas conhecidas para essas somas para entender o comportamento da função (isso ajuda tanto na implementação iterativa quanto na recursiva).
Passo 3
Fórmulas úteis (vou explicar e aplicar):
- A soma dos inteiros de
a é
Rápida justificativa: somando
e pareando termos dá essa fórmula clássica.
- Então
- E
porque são
termos iguais a
.
Somando as duas partes:
Portanto temos uma forma fechada (útil para conferir implementações):
Passo 4
Agora a forma iterativa (ideia): percorrer
de
a
acumulando os termos
. Vou escrever um pseudocódigo claro e explicar cada linha.
Pseudocódigo iterativo (linha a linha, explicado):
- Inicializar um acumulador
. Esse vai guardar a soma parcial. - Para cada inteiro
de até (inclusive), calcular o termo e somá-lo ao acumulador . - No final, retornar
.
Esse método reflete exatamente a definição da soma e funciona em tempo linear
. Vou mostrar um exemplo rápido para conferir: se
,
e a forma fechada dá
, conferido.
Passo 5
Detalhando o pseudocódigo iterativo com notação matemática (cada variável em TeX):
- Inicialize
. - Para
até faça: -
.
-
- Retorne
.
Explicação didática: começamos com soma zero; a cada iteração adicionamos o próximo termo da sequência
. Ao final,
contém a soma dos
termos.
Passo 6
Agora a forma recursiva (ideia): escrever
em função de
. Isso é direto a partir da definição da soma — a soma até
é a soma até
mais o último termo.
Derivação:
Precisamos de um caso base (quando parar a recursão). Para
,
Assim a definição recursiva fica clara:
- Caso base:
. - Passo recursivo: para
,
Passo 7
Vou mostrar como a recursão se desenrola com um exemplo (para que fique claro como resolver na prova):
Se ,
Se
E
Portanto
que bate com os resultados anteriores. Isso mostra que a recursão alcança o caso base e soma os termos corretamente.
Observação sobre eficiência: a versão recursiva acima tem custo linear em
e profundidade de recursão
. Se quiser uma versão recursiva que seja “tail-recursive” (útil em linguagens que otimizam cauda), pode-se usar um parâmetro acumulador, mas a forma pedida normalmente é a recursão direta que mostrei.
Resposta
a) Iterativa:
b) Recursiva: