Ficha 01 · Recursão e algoritmos
- Aplicar recursão
- Implementar pesquisa
- Reconhecer complexidade
- Comparar algoritmos
Parte I · Recursão
Exercício 1 · Identificar partes (10 pts)
Para esta função:
def potencia(base, exp):
if exp == 0:
return 1
return base * potencia(base, exp - 1)
a) Qual o caso base? (5 pts)
b) Qual o passo recursivo? (5 pts)
a) if exp == 0: return 1 — quando expoente chega a 0, retorna 1.
b) return base * potencia(base, exp - 1) — chama-se a si com expoente reduzido em 1, multiplicando pela base.
Exercício 2 · Implementar recursivamente (15 pts)
Implementa as seguintes funções recursivamente:
a) soma_natural(n) — soma 1 + 2 + ... + n.
b) contar_digitos(n) — quantos dígitos tem o número n (para n >= 0).
def soma_natural(n):
if n <= 0:
return 0
return n + soma_natural(n - 1)
print(soma_natural(5)) # 15
def contar_digitos(n):
if n < 10:
return 1
return 1 + contar_digitos(n // 10)
print(contar_digitos(12345)) # 5
Exercício 3 · Travessia de pastas (15 pts)
Implementa listar_recursivo(pasta) que imprime nomes de ficheiros/pastas indentados conforme profundidade. Usa os.listdir e os.path.isdir.
import os
def listar_recursivo(pasta, nivel=0):
try:
nomes = sorted(os.listdir(pasta))
except PermissionError:
return
for nome in nomes:
caminho = os.path.join(pasta, nome)
print(" " * nivel + nome)
if os.path.isdir(caminho):
listar_recursivo(caminho, nivel + 1)
listar_recursivo(".")
Parte II · Pesquisa
Exercício 4 · Pesquisa binária (15 pts)
Implementa pesquisa binária iterativa que devolve o índice do alvo (ou -1):
def binaria(lst, alvo):
lo, hi = 0, len(lst) - 1
while lo <= hi:
mid = (lo + hi) // 2
if lst[mid] == alvo:
return mid
elif lst[mid] < alvo:
lo = mid + 1
else:
hi = mid - 1
return -1
lst = [1, 3, 5, 7, 9, 11, 13, 15]
print(binaria(lst, 7)) # 3
print(binaria(lst, 4)) # -1
Exercício 5 · Comparar complexidades (10 pts)
Numa lista ordenada de 1 milhão de elementos, quantas comparações máximo faz cada algoritmo?
a) Pesquisa linear. ___
b) Pesquisa binária. ___
c) Diferença de tempo se cada comparação levar 1μs?
a) Pesquisa linear: até 1 000 000 comparações no pior caso.
b) Pesquisa binária: log₂(1 000 000) ≈ 20 comparações.
c) Linear: 1 000 000 × 1μs = 1 segundo. Binária: 20 × 1μs = 0.00002s = 20 microssegundos.
Binária é 50 000 vezes mais rápida. Por isso BDs usam índices B-tree (variação de pesquisa binária).
Parte III · Ordenação
Exercício 6 · Bubble sort melhorado (15 pts)
Implementa bubble sort que pára cedo se a lista já estiver ordenada (sem trocas numa passagem):
def bubble(lst):
n = len(lst)
for i in range(n):
trocou = False
for j in range(n - i - 1):
if lst[j] > lst[j+1]:
lst[j], lst[j+1] = lst[j+1], lst[j]
trocou = True
if not trocou:
break # já está ordenada
return lst
print(bubble([3, 1, 4, 1, 5, 9, 2, 6]))
Exercício 7 · Quicksort (20 pts)
Implementa quicksort recursivo. Compara com sorted() numa lista de 10 000 números aleatórios — quem é mais rápido?
import random
import time
def quicksort(lst):
if len(lst) <= 1:
return lst
pivot = lst[len(lst) // 2]
esq = [x for x in lst if x < pivot]
meio = [x for x in lst if x == pivot]
dir = [x for x in lst if x > pivot]
return quicksort(esq) + meio + quicksort(dir)
# Comparação
nums = [random.randint(0, 1_000_000) for _ in range(10_000)]
t = time.perf_counter()
quicksort(nums.copy())
print(f"quicksort: {time.perf_counter() - t:.4f}s")
t = time.perf_counter()
sorted(nums.copy())
print(f"sorted(): {time.perf_counter() - t:.4f}s")
sorted() é tipicamente 5-10× mais rápido porque é Timsort implementado em C, enquanto o quicksort acima é Python puro.
Lição: para produção, usar funções built-in. Implementar à mão só para aprender.