Considere a função calc indicada abaixo:
\operatorname{calc}(n)=\sum_{i=0}^{n} 4 i+5
a) Escreva a função calc de forma iterativa.
b) Escreva a função calc de forma recursiva.

Passo 1

O enunciado dá a função
\operatorname{calc}(n)=\sum_{i=0}^{n} 4 i+5
e pede duas coisas:
a) escrever \operatorname{calc} de forma iterativa;
b) escrever \operatorname{calc} de forma recursiva.
Informações importantes fornecidas pelo enunciado:
  • A soma é indexada por i de 0 até n.
  • Cada termo da soma é 4i+5.
  • 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
\operatorname{calc}(n)=\sum_{i=0}^{n} (4i+5),
ou seja, estamos somando, para cada i, o valor 4i+5.

Passo 2

Vamos entender a soma termo a termo. A soma é a soma de dois componentes:
\sum_{i=0}^{n} (4i+5)=\sum_{i=0}^{n} 4i + \sum_{i=0}^{n} 5.
Explicando cada parte:
  • \sum_{i=0}^{n} 4i é quatro vezes a soma dos inteiros de 0 a n.
  • \sum_{i=0}^{n} 5 é simplesmente 5 somado n+1 vezes (porque incluímos o i=0).
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 0 a n é
\sum_{i=0}^{n} i = \frac{n(n+1)}{2}.
Rápida justificativa: somando 0+1+2+\dots+n e pareando termos dá essa fórmula clássica.
  • Então
\sum_{i=0}^{n} 4i = 4\sum_{i=0}^{n} i = 4\cdot\frac{n(n+1)}{2}=2n(n+1).
  • E
\sum_{i=0}^{n} 5 = 5(n+1),
porque são n+1 termos iguais a 5.
Somando as duas partes:
\sum_{i=0}^{n} (4i+5)=2n(n+1)+5(n+1)=(n+1)(2n+5).
Portanto temos uma forma fechada (útil para conferir implementações):
\operatorname{calc}(n)=(n+1)(2n+5).

Passo 4

Agora a forma iterativa (ideia): percorrer i de 0 a n acumulando os termos 4i+5. Vou escrever um pseudocódigo claro e explicar cada linha.
Pseudocódigo iterativo (linha a linha, explicado):
  • Inicializar um acumulador \,s\leftarrow 0. Esse \,s vai guardar a soma parcial.
  • Para cada inteiro \,i de 0 até n (inclusive), calcular o termo \,4i+5 e somá-lo ao acumulador \,s.
  • No final, retornar \,s.
Esse método reflete exatamente a definição da soma e funciona em tempo linear O(n). Vou mostrar um exemplo rápido para conferir: se n=2,
\operatorname{calc}(2)=(4\cdot 0+5)+(4\cdot 1+5)+(4\cdot 2+5)=5+9+13=27,
e a forma fechada dá (2+1)(2\cdot 2+5)=3\cdot 9=27, conferido.

Passo 5

Detalhando o pseudocódigo iterativo com notação matemática (cada variável em TeX):
  • Inicialize \,s \leftarrow 0.
  • Para \,i=0 até \,n faça:
    • \,s \leftarrow s + (4i + 5).
  • Retorne \,s.
Explicação didática: começamos com soma zero; a cada iteração adicionamos o próximo termo da sequência 4i+5. Ao final, \,s contém a soma dos n+1 termos.

Passo 6

Agora a forma recursiva (ideia): escrever \operatorname{calc}(n) em função de \operatorname{calc}(n-1). Isso é direto a partir da definição da soma — a soma até n é a soma até n-1 mais o último termo.
Derivação:
\operatorname{calc}(n)=\sum_{i=0}^{n} (4i+5)=\left(\sum_{i=0}^{n-1} (4i+5)\right) + (4n+5)=\operatorname{calc}(n-1)+(4n+5).
Precisamos de um caso base (quando parar a recursão). Para n=0,
\operatorname{calc}(0)=4\cdot 0+5=5.
Assim a definição recursiva fica clara:
  • Caso base: \operatorname{calc}(0)=5.
  • Passo recursivo: para n\ge 1,
\operatorname{calc}(n)=\operatorname{calc}(n-1)+(4n+5).

Passo 7

Vou mostrar como a recursão se desenrola com um exemplo (para que fique claro como resolver na prova):
Se n=2,
\operatorname{calc}(2)=\operatorname{calc}(1)+(4\cdot 2+5).
E
\operatorname{calc}(1)=\operatorname{calc}(0)+(4\cdot 1+5)=5+(4+5)=14.
Portanto
\operatorname{calc}(2)=14+(8+5)=14+13=27,
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 n e profundidade de recursão n. 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:

\text{function }\operatorname{calc}(n):
\quad s \leftarrow 0
\quad\text{for } i = 0 \text{ to } n:\\ s \leftarrow s + (4i + 5)
\quad\text{return } s
b) Recursiva:

\operatorname{calc}(0)=5

\operatorname{calc}(n)=\operatorname{calc}(n-1)+(4n+5)\quad\text{para } n\ge 1

Exercícios relacionados