← DCC205 · Estruturas de Dados
DCC205 · Estruturas de Dados · 2026/2

Algoritmos iterativose recursão

Aula 03, completa. A A2 ensinou a comparar funções de custo \(T(n)\); aqui elas são construídas. No código iterativo, contando linha a linha. No recursivo, o custo de uma linha depende da própria função que estamos analisando — e a saída é escrever uma relação de recorrência e resolvê-la, por expansão ou desenhando a árvore de recursão. No fim, os dois casos em que a recursão cobra caro: o Fibonacci exponencial e a pilha de execução.

Aulas cobertas: A3 · aula completa Referência: CLRS, seções 2.2, 2.3.2 e 4.4 Atualizado: 20/08/2026
Parte 1Análise de algoritmos iterativos
A3 · 01

O método: custo × vezes

Definição · CLRS, pp. 25–26
  • Cada linha executa em tempo constante \(c_i\) — é o modelo RAM da Aula 01.
  • Logo, basta saber quantas vezes cada linha executa.

O custo total é a soma, linha a linha, de \(\text{custo}\times\text{vezes}\).

Exemplo · somando um vetor
LinhaCustoVezes
soma = 0;\(c_1\)\(1\)
for (i = 0; i < n; i++)\(c_2\)\(n+1\)
  soma += v[i];\(c_3\)\(n\)

Somando:

$$T(n) = c_1 + c_2(n+1) + c_3\,n = a\,n + b \;\Rightarrow\; \Theta(n)$$
O \(n+1\) que todo mundo esqueceO teste do for executa uma vez a mais que o corpo: a última avaliação é a que falha e encerra o laço. Corpo \(n\) vezes, teste \(n+1\).
A3 · 02

Exemplo 1 · dois laços

funclaço simples + laço duplo
  1. void func(int *v, int n) {
  2. int i, j, sum = 0;
  3. for (i = 0; i < n; i++)
  4. sum += v[i];
  5. for (i = 1; i < n; i++)
  6. for (j = 1; j < n; j++)
  7. sum += v[j];
  8. }
Laço simples · linhas 3–4

i percorre \(0,1,\dots,n-1\): o corpo executa \(n\) vezes e o teste, \(n+1\).

$$c_2(n+1) + c_3\,n = \Theta(n)$$
Laço duplo · linhas 5–7

Externo: i vai de \(1\) a \(n-1\), ou seja \(n-1\) iterações. Para cada valor de i, o interno roda \(n-1\) vezes.

$$(n-1)\times(n-1) = (n-1)^2 = \Theta(n^2)$$
Juntando tudo $$T(n) = \underbrace{\Theta(n)}_{\text{laço simples}} + \underbrace{\Theta(n^2)}_{\text{laço duplo}} = a\,n^2 + b\,n + c$$

Pela Aula 02, termos de menor ordem e constantes não importam: \(T(n)=\Theta(n^2)\). E dá para afirmar \(\Theta\), não apenas \(O\), porque a contagem foi exata e vale para toda entrada.

A regra que a prova cobraLaços aninhados multiplicam contagens; laços em sequência somam. Trocar uma coisa pela outra transforma \(\Theta(n)\) em \(\Theta(n^2)\) — e vice-versa.
A3 · 03

Exemplo 2 · Max, e quando melhor caso = pior caso

Maxda Aula 01
  1. int Max(int *A, int n) {
  2. int i, temp;
  3. temp = A[0];
  4. for (i = 1; i < n; i++)
  5. if (temp < A[i])
  6. temp = A[i];
  7. return temp;
  8. }
Contagem

O laço roda \(n-1\) vezes e cada iteração faz 1 comparação de elementos (temp < A[i]). Total: \(n-1\) comparações, sempre.

$$T(n)=\Theta(n)$$

A atribuição temp = A[i] pode ou não executar, mas ela só altera a constante, nunca a ordem.

Observação útil · usada de novo já já

Se o custo é \(\Omega(f(n))\) no melhor caso e \(O(f(n))\) no pior caso, então o algoritmo é \(\Theta(f(n))\) — sem precisar analisar o caso médio.

O caso médio está sempre imprensado entre o melhor e o pior.

A3 · 04

Exemplos 3 e 4 · MaxMin1 e MaxMin2

Os dois algoritmos acham o maior e o menor de uma vez. A diferença é uma única palavra: o else.

MaxMin1dois ifs independentes
  1. void MaxMin1(int *A, int n,
  2. int *Max, int *Min) {
  3. int i;
  4. *Max = A[0]; *Min = A[0];
  5. for (i = 1; i < n; i++) {
  6. if (A[i] > *Max) *Max = A[i];
  7. if (A[i] < *Min) *Min = A[i];
  8. }
  9. }
MaxMin1 · custo

Laço com \(n-1\) iterações, e cada iteração faz 2 comparações de elementos — os dois if sempre executam.

$$2(n-1)\ \text{comparações, para toda entrada} \;\Rightarrow\; T(n)=\Theta(n)$$
MaxMin2o segundo if virou else if
  1. void MaxMin2(int *A, int n,
  2. int *Max, int *Min) {
  3. int i;
  4. *Max = A[0]; *Min = A[0];
  5. for (i = 1; i < n; i++) {
  6. if (A[i] > *Max) *Max = A[i];
  7. else if (A[i] < *Min) *Min = A[i];
  8. }
  9. }

Agora a 2ª comparação só executa se a 1ª falhar — o custo passa a depender da entrada.

CasoEntradaComparações
Melhorvetor crescente: A[i] > *Max é sempre verdadeiro, o else nunca executa\(n-1\)
Piorvetor decrescente: a 1ª comparação sempre falha, a 2ª sempre executa\(2(n-1)\)
Médioalgo entre os doisnão precisa calcular
Pela observação do Max

Melhor caso \(\Omega(n)\) e pior caso \(O(n)\) têm a mesma ordem, logo \(T(n)=\Theta(n)\) para toda entrada. O caso médio vem de brinde.

MaxMin1 e MaxMin2 estão ambos em \(\Theta(n)\) — diferem só na constante. Na Aula 02 vimos que, dentro da mesma classe, é a constante que decide.

A3 · 05

Exemplo 5 · pesquisa sequencial

Pesquisapara ao encontrar
  1. int Pesquisa(TipoRegistro *A,
  2. int n, int chave) {
  3. int i = 0;
  4. while (i < n) {
  5. if (A[i].chave == chave)
  6. break;
  7. i++;
  8. }
  9. return i;
  10. }

O break faz o custo depender de onde a chave está.

CasoSituaçãoComparações · ordem
Melhorchave na posição 0\(1\) comparação \(\Rightarrow \Theta(1)\)
Piorchave ausente, ou na última posição\(n\) comparações \(\Rightarrow \Theta(n)\)
Médiochave presente, posições equiprováveis\(\frac{n+1}{2}\) comparações \(\Rightarrow \Theta(n)\)

O caso médio entra como resultado citado: a derivação usa probabilidade (CLRS, seção 5.2).

Atenção · aqui não existe \(\Theta\) únicoMelhor caso \(\Theta(1)\) e pior caso \(\Theta(n)\) têm ordens diferentes, então a observação do Max não se aplica. O máximo que se pode afirmar do algoritmo como um todo é \(T(n)=O(n)\) e \(T(n)=\Omega(1)\). Escrever “a pesquisa sequencial é \(\Theta(n)\)” sem dizer pior caso é erro.
A3 · Exercício

Laços em sequência

Qual a ordem de complexidade do trecho?

Checkpoint (a)dois laços, um depois do outro
  1. for (i = 0; i < n; i++) s += A[i];
  2. for (j = 0; j < n; j++) s += B[j];
Resolução $$n + n = 2n \;\Rightarrow\; \Theta(n)$$

Laços em sequência somam, não multiplicam. Nenhum dos dois está dentro do outro.

A3 · Exercício

Laço interno que depende de i

E agora, com o limite do laço interno preso ao índice externo?

Checkpoint (b)laço duplo triangular
  1. for (i = 0; i < n; i++)
  2. for (j = 0; j <= i; j++)
  3. s += M[i][j];
Resolução

Para cada \(i\), o interno roda \(i+1\) vezes (de \(j=0\) até \(j=i\)). A contagem vira um somatório:

$$\sum_{i=0}^{n-1}(i+1) = \frac{n(n+1)}{2} \;\Rightarrow\; \Theta(n^2)$$

Metade do laço duplo completo — mas a ordem final é a mesma, porque a constante \(\tfrac12\) some no \(\Theta\).

Parte 2Recursão e pilha de execução
A3 · 06

O algoritmo misterioso

Abrindo a parte 2, um exercício de leitura: o que esta função calcula?

XXXXXo que ela calcula?
  1. int XXXXX(int n) {
  2. int r = n;
  3. n--;
  4. while (n > 0) {
  5. r *= n;
  6. n--;
  7. }
  8. return r;
  9. }
Resposta e análise

\(r\) acumula \(n\cdot(n-1)\cdot(n-2)\cdots 2\cdot 1\): é o fatorial, \(n!\).

Pelo método custo × vezes: o laço roda \(n-1\) vezes com corpo constante.

$$T(n)=\Theta(n)$$
A3 · 07

A versão recursiva e o círculo

Fatoriala mesma matemática
  1. int Fatorial(int n) {
  2. if (n <= 0)
  3. return 1;
  4. else
  5. return n * Fatorial(n-1);
  6. }

É a definição matemática escrita literalmente: \(n! = n\cdot(n-1)!\). Mas quantas “operações” custa a linha 5?

O problema

O custo dessa linha depende do custo da própria função que estamos analisando. Contar linha a linha entra em círculo: para saber \(T(n)\) eu precisaria já saber \(T(n-1)\), que precisa de \(T(n-2)\)…

O método da parte 1, sozinho, não fecha aqui.

A ferramenta que quebra o círculo — transformar essa circularidade em uma relação de recorrência e resolvê-la — é o assunto da parte 3.

A3 · 08

Anatomia de uma função recursiva

Antes de resolver o círculo, a revisão de como a recursão funciona. Toda função recursiva tem duas partes, e as linhas do Fatorial acima se dividem exatamente entre elas.

1 · Caso base — linhas 2–3

A função não chama a si mesma; devolve uma resposta direta. É a condição de parada.

2 · Caso recursivo — linha 5

A função chama a si mesma com uma entrada menor, aproximando-se do caso base.

Guarde essa estrutura: a ferramenta de análise que vem depois espelha exatamente essas duas partes — caso base do algoritmo vira caso base de \(T\), chamada recursiva vira um termo \(T(\text{entrada menor})\).

Observação 1 · recursão não precisa ser direta

Uma função \(A\) pode chamar \(B\), e \(B\) chamar \(A\) de volta — é a recursão indireta (ou mútua). A análise é a mesma.

Observação 2 · cada chamada ocupa memória

Toda chamada de função cria um registro de ativação — parâmetros, variáveis locais, endereço de retorno — na pilha de execução. Ele só é liberado quando a chamada retorna.

A3 · 09

A pilha de execução: \(fat(4)\) passo a passo

fat + maino programa que vamos executar
  1. int fat(int n) {
  2. if (n <= 0)
  3. return 1;
  4. return n * fat(n-1);
  5. }
  7. int main() {
  8. int f = fat(4);
  9. printf("%d", f);
  10. }
Exemplo · a pilha, do topo para a base

A pilha cresce para cima. Leia a coluna do meio de baixo para cima (a descida) e a da direita de cima para baixo (a volta).

RegistroFase 1 · empilhaFase 2 · desempilha
fat(0)testa \(n\le 0\) → caso basedevolve \(1\)
fat(1)chama fat(0)\(1\cdot 1 = 1\)
fat(2)chama fat(1)\(2\cdot 1 = 2\)
fat(3)chama fat(2)\(3\cdot 2 = 6\)
fat(4)chama fat(3)\(4\cdot 6 = 24\)
main()chama fat(4)\(f = 24\)

Fase 1: empilha até o caso base. Fase 2: desempilha multiplicando na volta — nenhuma multiplicação acontece na descida.

No pico, \(n+1\) registros de fat coexistem na pilha. Esse pico volta na parte 6, quando o custo de espaço entra na conta.

Parte 3Relações de recorrência
A3 · 10

O que é uma relação de recorrência

Definição

Uma relação de recorrência define uma função \(T(n)\) em termos de seu próprio valor em entradas menores — mais os casos base, que encerram a definição.

Aqui \(T(n)\) é o tempo de execução do algoritmo para uma entrada de tamanho \(n\).

O que torna a ferramenta natural é que ela espelha o algoritmo: as duas partes da anatomia do tópico 08 viram as duas partes da recorrência, uma a uma.

código caso base if (n <= 0) return 1; caso recursivo return n * fat(n-1); recorrência encerra a definição T(0) = c chama T de novo T(n) = T(n−1) + d
Caso base do algoritmo vira caso base de T; chamada recursiva vira um termo T(entrada menor). Extrair a recorrência é ler o código duas vezes, uma metade de cada vez.
Plano de ataque · dois passos
  1. Extrair a recorrência do código.
  2. Resolvê-la, achando a ordem \(\Theta\) de \(T(n)\).
A3 · 11

Extraindo a recorrência do Fatorial

Passo 1, feito sobre o mesmo Fatorial do tópico 07.

Caso base · linhas 2–3

O caso mais simples é \(n=0\): testa e devolve 1. Trabalho constante — chame de \(c>0\).

$$T(0) = c$$
Caso recursivo · linha 5

Fora da chamada há teste, produto e retorno: custo constante \(d\). E a chamada Fatorial(n-1) custa, por definição, \(T(n-1)\).

$$T(n) = T(n-1) + d,\quad n \ge 1$$
A recorrência completa $$T(n) = \begin{cases} c & \text{se } n = 0 \quad \text{(caso base)}\\[4pt] T(n-1) + d & \text{se } n \ge 1 \quad \text{(caso recursivo)} \end{cases}$$

Compacta e válida para todo \(n\) — mas ainda não responde: \(T(n)\) é \(\Theta\) de quê?

Repare no que aconteceu: o círculo do tópico 07 virou ferramenta. Em vez de fugir da circularidade, usamos o próprio \(T\) para nomear o custo da chamada — e agora é um problema de álgebra, não de contagem.

A3 · 12

Resolvendo por expansão

Receita · três passos
  1. Expanda \(T\) algumas vezes — 2 ou 3 costumam bastar.
  2. Escreva o termo geral após \(k\) expansões.
  3. Descubra o \(k\) que atinge o caso base e substitua.

Também chamado de método da iteração, ou expansão telescópica.

Expandindo \(T(n)=T(n-1)+d\) $$T(n) = T(n-1) + d$$ $$= \big[T(n-2) + d\big] + d = T(n-2) + 2d$$ $$= \big[T(n-3) + d\big] + 2d = T(n-3) + 3d$$ $$\;\vdots$$ $$= T(n-k) + k\,d \qquad \text{(termo geral)}$$
Onde parar, e o resultado

No caso base: \(n-k=0 \Rightarrow k=n\). São \(n\) expansões — uma por chamada recursiva. Substituindo:

$$T(n) = \underbrace{T(0)}_{=\,c} + n\,d = d\,n + c \;\Rightarrow\; \Theta(n)$$

Mesma ordem da versão iterativa do tópico 06 — e faz sentido: as duas fazem \(n\) multiplicações. As constantes \(c\) e \(d\) sumiram no \(\Theta\): nunca foi preciso conhecê-las, só saber que são constantes.

O passo que erra na prova é o \(k\)Expandir 2 ou 3 vezes é a parte fácil. O que decide a resposta é resolver \(n-k=\text{base}\): com caso base em \(n=0\) dá \(k=n\), mas com base em \(n=1\) — como no Imprime da parte 4 — daria \(k=n-1\). Errar aí troca o termo geral inteiro.
A3 · Exercício

Soma recursiva de vetor

Escreva e resolva a recorrência deste algoritmo.

Somacheckpoint da parte 3
  1. int Soma(int *v, int n) {
  2. if (n == 0) return 0;
  3. return v[n-1] + Soma(v, n-1);
  4. }
Resolução

Caso base: \(T(0)=c\). Caso recursivo: trabalho constante \(d\) mais uma chamada com \(n-1\).

$$T(n) = T(n-1) + d \;\Rightarrow\; T(n)=\Theta(n)$$

É a mesma recorrência do fatorial — não precisa expandir de novo.

MoralAlgoritmos diferentes podem ter a mesma recorrência: ela captura a estrutura das chamadas, não a operação realizada. Multiplicar ou somar dá no mesmo — o que conta é quanto a entrada encolhe e quantas chamadas saem de cada nível.
Parte 4Árvore de recursão
A3 · 13

Quando a entrada é dividida

Até aqui a entrada encolhia de 1 em 1. Agora um algoritmo que divide: imprime o primeiro elemento e, se \(n>1\), chama a si mesmo para a segunda metade do vetor.

Imprimeuma chamada, metade da entrada
  1. void Imprime(int *v, int n) {
  2. printf("%d\n", v[0]);
  3. if (n > 1)
  4. Imprime(v + n/2, n - n/2);
  5. }
A recorrência

Trabalho local constante (um printf) e uma chamada com entrada de tamanho \(\approx n/2\):

$$T(n) = \begin{cases} c & \text{se } n = 1\\[4pt] T(n/2) + c & \text{se } n > 1 \end{cases}$$

Seguindo o CLRS (p. 88), vamos suprimir pisos e tetos e supor \(n\) potência de 2. Esse desleixo controlado não altera a ordem de crescimento e é padrão na literatura.

A3 · 14

A árvore de recursão

Expandir \(T(n-1)\) era fácil: uma linha por passo. Com \(T(n/2)\) — e pior, com duas chamadas — a expansão vira um emaranhado. A árvore de recursão organiza a mesma conta em um desenho.

O contrato da árvore · como ler o desenho
  • Cada nó é uma chamada da função, anotada com o custo local dela — sem contar as chamadas filhas.
  • Os filhos de um nó são as chamadas recursivas que ele faz.

E somar tem dois passos: 1. some os custos dentro de cada nível; 2. some os totais dos níveis.

custo n c n / 2 c n / 4 c 1 c caso base log₂ n + 1 níveis
Uma chamada por nó: a árvore degenera em caminho. Cada nível tem 1 nó de custo c, então o total é o número de níveis vezes c.
Passo 1 · profundidade

O tamanho cai pela metade a cada nível:

$$\frac{n}{2^0},\; \frac{n}{2^1},\; \frac{n}{2^2},\; \dots,\; \frac{n}{2^k} = 1 \;\Longrightarrow\; 2^k = n \;\Longrightarrow\; k = \log_2 n$$

Logo a árvore tem \(\log_2 n + 1\) níveis — do nível 0 ao nível \(\log_2 n\).

Passo 2 · somar

Cada nível custa \(c\):

$$T(n) = c\,(\log_2 n + 1) = c\log_2 n + c \;\Rightarrow\; \Theta(\log n)$$
A3 · 15

Duas chamadas: a árvore do merge sort

Mesmo esqueleto, dois ajustes: o trabalho local vira uma varredura linear, e agora são duas chamadas, uma para cada metade.

ImprimeMaxduas chamadas, trabalho local linear
  1. void ImprimeMax(int *v, int n) {
  2. int i, max = v[0];
  3. for (i = 1; i < n; i++) /* custo c n */
  4. if (v[i] > max) max = v[i];
  5. printf("%d\n", max);
  6. if (n > 1) {
  7. ImprimeMax(v, n/2);
  8. ImprimeMax(v + n/2, n - n/2);
  9. }
  10. }
A recorrência — e onde você já a viu $$T(n) = \begin{cases} c & \text{se } n = 1\\[4pt] 2\,T(n/2) + c\,n & \text{se } n > 1 \end{cases}$$

É a recorrência do merge sort (CLRS, eq. 2.1). O que fizermos aqui vale lá.

soma do nível c n c n c n/2 c n/2 c n c n/4 c n/4 · · · c n/4 c n/4 c n c c c c c n n folhas de custo c
Os nós dobram a cada nível e o custo de cada um cai pela metade: as duas coisas se cancelam, e todo nível soma exatamente cn — inclusive o fundo, onde n folhas custam c cada.
Passo 1 · profundidade e conferência

O tamanho cai à metade por nível, igual ao caso anterior: \(n/2^k = 1 \Rightarrow k=\log_2 n\), ou seja \(\log_2 n + 1\) níveis.

Confere pelas folhas: com \(\log_2 n\) duplicações, o último nível tem \(2^{\log_2 n} = n\) folhas. ✓

Passo 2 · somar os níveis $$T(n) = \underbrace{c\,n + c\,n + \dots + c\,n}_{\log_2 n\,+\,1\ \text{níveis}} = c\,n\log_2 n + c\,n \;\Rightarrow\; \Theta(n\log n)$$

O custo do merge sort, provado com um desenho.

A armadilha do \(n/2\)“Tem \(n/2\), então é \(\log n\)” só vale para uma chamada com trabalho local constante. Aqui a entrada também é dividida por 2, e mesmo assim o custo é \(\Theta(n\log n)\): quem mudou tudo foi o número de chamadas e o custo local.
A3 · 16

Os padrões que já sabemos resolver

RecorrênciaEstrutura do algoritmoSolução
\(T(n-1) + c\)1 chamada, reduz 1, local constante\(\Theta(n)\)
\(T(n/2) + c\)1 chamada, metade, local constante\(\Theta(\log n)\)
\(2\,T(n/2) + c\,n\)2 chamadas, metades, local linear\(\Theta(n\log n)\)
O padrão por trás da tabela

Três perguntas decidem a classe: quanto reduz a entrada, quantas chamadas saem de cada nó e quanto custa o trabalho local.

Falta uma linha nessa tabela: e se forem duas chamadas que reduzem a entrada de 1 em 1? Esse é o Fibonacci, e a resposta é exponencial — é a parte 5, a seguir.

Vale o aviso honesto do slide: os exemplos de hoje foram bem comportados, com divisão exata e custo local simples. Para \(3T(n/4)+c\,n^2\) ou \(7T(n/2)+n^2\), desenhar e somar níveis vira conta longa e sujeita a erro — e é por isso que existe o método mestre (CLRS, seção 4.5), assunto da próxima aula, que a árvore de hoje justamente prova.

Parte 5Fibonacci: o custo de repetir trabalho
A3 · 17

Fibonacci recursivo

O caso que faltava na tabela: duas chamadas que reduzem a entrada de 1 em 1.

Fibonaccio código é a definição
  1. int Fibonacci(int n) {
  2. if (n < 3)
  3. return 1;
  4. return Fibonacci(n-1)
  5. + Fibonacci(n-2);
  6. }

É a definição matemática escrita literalmente — \(F_1=F_2=1\) e \(F_n=F_{n-1}+F_{n-2}\). Elegante. E quanto custa?

A recorrência · mesmo procedimento de sempre $$T(n) = \begin{cases} c & \text{se } n < 3\\[4pt] T(n-1) + T(n-2) + d & \text{se } n \ge 3 \end{cases}$$

Dois termos recursivos, de tamanhos diferentes. Expandir direto fica feio: cada expansão duplica a quantidade de termos, e eles nem sequer são iguais entre si.

A3 · 18

A desigualdade-chave e o teto \(O(2^n)\)

A saída

\(T\) é crescente — entrada maior nunca custa menos. Então \(T(n-2)\le T(n-1)\), e dá para trocar o termo menor pelo maior:

$$T(n) \;\le\; 2\,T(n-1) + d$$

Trocamos a recorrência por uma mais simples que a limita por cima: o que provarmos para ela vale como \(O\) para a original.

Expandindo o teto $$T(n) \le 2\,T(n-1) + d$$ $$\le 2\big[2\,T(n-2)+d\big] + d = 4\,T(n-2) + 3d$$ $$\le 8\,T(n-3) + 7d$$ $$\;\vdots$$ $$\le 2^k\,T(n-k) + (2^k-1)\,d \qquad \text{(termo geral)}$$

O caso base é \(n<3\), então paramos em \(n-k=2 \Rightarrow k=n-2\):

$$T(n) \;\le\; 2^{\,n-2}c + (2^{\,n-2}-1)\,d \;\Rightarrow\; O(2^n)$$

O número de chamadas dobra a cada nível: crescimento exponencial.

A ordem exata

Com mais matemática — as raízes do polinômio característico \(x^2=x+1\) — chega-se ao limite justo:

$$T(n)=\Theta(\varphi^{\,n}), \qquad \varphi=\frac{1+\sqrt5}{2}=1{,}61803\dots \quad \text{(razão áurea)}$$
Teto folgado ainda é tetoUsar \(T(n-2)\le T(n-1)\) foi um exagero deliberado: por isso o resultado sai como \(O(2^n)\) e não como \(\Theta\). A ordem exata é \(1{,}618^n\), que cresce mais devagar que \(2^n\) — mas continua exponencial, e a classe não muda de natureza.
A3 · 19

A árvore entrega o culpado

Por que tanto? A árvore de recursão da parte 4, desenhada para \(F_5\), mostra o problema em um golpe de vista.

F₃ · 2 vezes F₂ · 3 vezes F₅ F₄ F₃ F₃ F₂ F₂ F₁ F₂ F₁ o mesmo subproblema, resolvido do zero em cada aparição
A subárvore inteira de F₃ é calculada duas vezes, e F₂ três vezes — só para n = 5. A recursão não guarda resultado nenhum: cada chamada refaz todo o trabalho.
Exponencial na prática

O número de chamadas é \(\approx 2F_n-1\). Supondo \(10^8\) operações por segundo:

\(n\)ChamadasTempo
30\(\approx 1{,}7\times10^{6}\)\(\approx 0{,}02\) s — imperceptível
50\(\approx 2{,}5\times10^{10}\)\(\approx 4\) min — um cafezinho
100\(\approx 7\times10^{20}\)\(\approx 2\times10^{5}\) anos — civilizações inteiras

Ir de \(n=50\) para \(n=100\) não dobra o tempo: multiplica por \(\sim 10^{10}\). É isso que “exponencial” significa.

A3 · 20

A alternativa iterativa

FibIterguarda os dois últimos e avança
  1. int FibIter(int n) {
  2. int fn1 = 1, fn2 = 1, fn, i;
  3. if (n < 3) return 1;
  4. for (i = 3; i <= n; i++) {
  5. fn = fn2 + fn1;
  6. fn2 = fn1;
  7. fn1 = fn;
  8. }
  9. return fn;
  10. }
Custo

Guarda só os 2 últimos valores e avança; nenhum subproblema é recalculado. O laço roda \(n-2\) vezes com corpo constante.

$$T(n)=\Theta(n)$$

Para \(n=100\): recursivo \(\sim 10^{20}\) operações, iterativo \(\sim 100\).

Dá para fazer ainda melhor — \(\Theta(\log n)\) com exponenciação rápida de matrizes —, mas isso fica fora do escopo da disciplina.

Parte 6Iterativo ou recursivo?
A3 · 21

Mesma tarefa, memórias diferentes

Volte ao fatorial do tópico 09 e olhe as duas versões no pico de uso da pilha, para \(n=4\).

iterativo recursivo fat(4) main() 1 registro de ativação, para qualquer n cresce fat(0) fat(1) fat(2) fat(3) fat(4) main() n + 1 registros simultâneos no pico
O mesmo resultado, 24, com duas ocupações de memória diferentes. O vazio do lado esquerdo é a mensagem: o laço reaproveita um quadro só, enquanto a recursão precisa manter todos abertos até o caso base devolver.
A3 · 22

Complexidade de espaço

AlgoritmoTempoEspaço (pilha)
Fatorial iterativo\(\Theta(n)\)\(\Theta(1)\)
Fatorial recursivo\(\Theta(n)\)\(\Theta(n)\)

Mesmo tempo, espaços diferentes: a pilha de execução é custo, e não aparece se olharmos só o tempo. O Fibonacci recursivo, esse, perdia nos dois critérios.

A moral, com nuance

Recursão nem sempre é a melhor escolha — mesmo quando o problema é definido recursivamente.

Mas ela não é vilã: no merge sort da parte 4 a pilha tem profundidade \(\Theta(\log n)\), um preço ínfimo pela clareza de um dividir-para-conquistar.

Parte 7Quadro final e exercícios
A3 · 23

Padrões de reconhecimento rápido

A tabela do tópico 16, agora com a linha que faltava.

Se o algoritmo…RecorrênciaClasse
reduz 1, faz 1 chamada, local \(O(1)\)\(T(n-1)+c\)\(\Theta(n)\)
divide por 2, faz 1 chamada, local \(O(1)\)\(T(n/2)+c\)\(\Theta(\log n)\)
divide por 2, faz 2 chamadas, local \(O(n)\)\(2T(n/2)+c\,n\)\(\Theta(n\log n)\)
reduz 1, faz 2 chamadas\(T(n-1)+T(n-2)+c\)\(\Theta(\varphi^{\,n})\)
As duas armadilhas clássicas“Tem \(n/2\), então é \(\log n\)” — só se for uma chamada com trabalho local constante. E não confunda número total de chamadas (tempo) com profundidade da pilha (espaço): em Fibonacci são \(\sim\varphi^n\) chamadas, mas a pilha nunca passa de \(n\) registros.
A3 · Exercício

Classifique sem desenhar

Para cada recorrência, diga a ordem \(\Theta\) — usando expansão ou a árvore mental.

1 · \(T(n)=T(n/2)+c\)

Caminho com \(\log_2 n\) níveis de custo \(c\).

$$\Rightarrow\; \Theta(\log n)$$
2 · \(T(n)=T(n-1)+c\,n\)

Padrão novo: reduz 1, mas com trabalho local linear. Expandindo:

$$c\,n + c(n-1) + \dots + c = c\,\frac{n(n+1)}{2} \;\Rightarrow\; \Theta(n^2)$$
3 · \(T(n)=2\,T(n-1)+c\)

Dobra a cada passo e reduz só 1 — o termo geral é \(2^k\,T(n-k)\).

$$\Rightarrow\; \Theta(2^n)$$
O que o item 2 ensinaDividir a entrada é o que gera o \(\log\). Reduzir de 1 em 1 com trabalho linear em cada nível dá um somatório de Gauss, e o resultado é quadrático — é o custo do insertion sort no pior caso, visto na A2.
A3 · 24

Exercícios propostos e referências

Para fixar · do slide de fecho
  1. Escrever a busca binária recursiva, extrair a recorrência e resolvê-la pela árvore. Esperado: \(T(n)=T(n/2)+c \Rightarrow \Theta(\log n)\).
  2. Resolver \(T(n)=T(n-1)+c\,n\) por expansão e dizer que algoritmo conhecido tem esse custo no pior caso.
  3. Desenhar a árvore de \(T(n)=4T(n/2)+c\,n\) e mostrar que a soma por nível cresce ao descer. Qual a ordem?
  4. Modificar o Fibonacci recursivo para guardar resultados já computados em um vetor. Qual passa a ser o custo de tempo? E o de espaço?
  5. Do CLRS: exercícios 2.3-3 e 4.4-1.

Os itens 3 e 4 são os que mais rendem: o primeiro é o caso em que o custo se concentra nas folhas — o que prepara o método mestre; o segundo é a ponte para programação dinâmica.

Referências da aula

CLRS, Introduction to Algorithms, 3ª ed., MIT Press, 2009:

  • Seção 2.2 — Analyzing algorithms: custo × vezes, melhor e pior caso (pp. 23–27).
  • Seção 2.3.2 — Analyzing divide-and-conquer algorithms: a recorrência do merge sort (pp. 34–37).
  • Seção 4.4 — The recursion-tree method (pp. 88–92).
  • Seção 4.5 — The master method: a próxima aula.

Complementar: Jeff Erickson, Algorithms, capítulo 1 (Recursion), disponível gratuitamente online.

FechoChecklist da aula
Revisão

Checklist da A3

Se você consegue responder tudo abaixo sem consultar, a aula está fechada.

PerguntaOnde está
Montar a tabela custo × vezes de um trecho e chegar em \(T(n)\)O método: custo × vezes
Dizer quantas vezes o teste de um for executa, e por que é uma a mais que o corpoO método: custo × vezes
Decidir, num código com vários laços, o que soma e o que multiplicaDois laços
Justificar por que a resposta é \(\Theta\) e não apenas \(O\)Dois laços
Contar as comparações do Max e concluir \(\Theta(n)\) sem olhar o caso médioMax
Enunciar a observação “melhor \(\Omega(f)\) + pior \(O(f)\) ⇒ \(\Theta(f)\)”Max
Exibir a entrada de melhor e a de pior caso do MaxMin2, com a contagem de cada umaMaxMin1 e MaxMin2
Explicar por que MaxMin1 e MaxMin2 estão na mesma classe mesmo contando diferenteMaxMin1 e MaxMin2
Dizer por que a pesquisa sequencial não tem \(\Theta\) único, e o que sobra afirmarPesquisa sequencial
Resolver o somatório \(\sum_{i=0}^{n-1}(i+1)\) de um laço duplo triangularExercício · laço interno
Identificar caso base e caso recursivo em uma função dadaAnatomia
Explicar por que contar linha a linha não fecha num algoritmo recursivoA versão recursiva
Desenhar a pilha de \(fat(4)\) e dizer em que fase cada multiplicação aconteceA pilha de execução
Extrair a recorrência de um código recursivo, caso base e caso recursivoExtraindo do código
Expandir \(T(n)=T(n-1)+d\), escrever o termo geral e achar o \(k\) do caso baseResolvendo por expansão
Explicar por que dois algoritmos diferentes podem cair na mesma recorrênciaExercício · soma recursiva
Enunciar o contrato da árvore: o que é um nó, o que são os filhos, como somarA árvore de recursão
Achar a profundidade resolvendo \(n/2^k = 1\) e contar \(\log_2 n + 1\) níveisA árvore de recursão
Mostrar que em \(2T(n/2)+cn\) todo nível soma \(cn\), e concluir \(\Theta(n\log n)\)Duas chamadas
Conferir a profundidade pelo número de folhas, \(2^{\log_2 n}=n\)Duas chamadas
Dizer as três perguntas que decidem a classe de uma recorrênciaOs padrões
Escrever a recorrência do Fibonacci e dizer por que a expansão direta não fechaFibonacci recursivo
Usar \(T(n-2)\le T(n-1)\) para obter o teto, e justificar por que sai \(O\) e não \(\Theta\)A desigualdade-chave
Dar a ordem exata do Fibonacci recursivo e de onde vem o \(\varphi\)A desigualdade-chave
Explicar, pela árvore, por que o custo explode — e o que a recursão deixa de guardarA árvore entrega o culpado
Escrever o Fibonacci iterativo e justificar o \(\Theta(n)\)A alternativa iterativa
Comparar tempo e espaço do fatorial nas duas versõesComplexidade de espaço
Dizer por que a recursão do merge sort não é cara em espaçoComplexidade de espaço
Classificar \(T(n)=T(n-1)+c\,n\) e dizer que algoritmo tem esse custo no pior casoExercício · classifique
Não confundir número de chamadas (tempo) com profundidade da pilha (espaço)Padrões de reconhecimento