aulify · Sebenta

UC · Unidade de Competência · UC00607

Programação estruturada · complexidade superior

Sebenta · Recursão, algoritmos, módulos, testes

50h · 4.5 pontos crédito Curso: T. Desenv. Software ↗ Referencial oficial SNQ

Apresentação

UC00607 (50h · 4,5 pts) é a continuação directa da UC00606. Os fundamentos da linguagem estão dados; agora produzimos programas maiores, com mais de um módulo, manipulação de dados estruturados (JSON, CSV, APIs) e testes automatizados.

Recursão

Princípio

Função que se chama a si própria.

Duas partes obrigatórias: 1. Caso base — condição para parar. 2. Passo recursivo — chama-se a si com problema menor.

def factorial(n):
    if n <= 1:                  # caso base
        return 1
    return n * factorial(n - 1) # passo recursivo

Sem caso base, recursão é infinita e provoca RecursionError: maximum recursion depth exceeded. Python limita a ~1000 níveis por defeito.

Exemplos clássicos

Fibonacci:

def fib(n):
    if n < 2:
        return n
    return fib(n-1) + fib(n-2)

Esta versão é exponencial, lenta para n > 30. Versão com memoização:

from functools import lru_cache

@lru_cache(maxsize=None)
def fib(n):
    if n < 2:
        return n
    return fib(n-1) + fib(n-2)

Travessia recursiva de directorias:

import os

def listar_recursivo(pasta, nivel=0):
    for nome in sorted(os.listdir(pasta)):
        caminho = os.path.join(pasta, nome)
        print("  " * nivel + nome)
        if os.path.isdir(caminho):
            listar_recursivo(caminho, nivel + 1)

Recursão vs iteração

Maioria dos problemas pode ser feita com qualquer das duas. Recursão é mais expressiva mas: - Consome mais memória (stack frames). - Pode ser mais lenta. - Limite de profundidade.

Recursão brilha em problemas naturalmente recursivos: - Travessia de árvores / grafos. - Fractais. - Quicksort, mergesort. - Backtracking (Sudoku, labirintos).

Algoritmos

Pesquisa

Linear (sequencial) — O(n):

def linear(lst, alvo):
    for i, v in enumerate(lst):
        if v == alvo:
            return i
    return -1

Binária — O(log n), requer lista ordenada:

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

Em listas grandes, binária é dramaticamente mais rápida. Em 1 milhão de elementos, linear pode precisar de 1M comparações; binária precisa de 20.

Ordenação

Bubble sort (didáctico, O(n²)):

def bubble(lst):
    n = len(lst)
    for i in range(n):
        trocou = False
        for j in range(0, 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
    return lst

Selection sort (didáctico, O(n²)):

def selection(lst):
    n = len(lst)
    for i in range(n):
        min_idx = i
        for j in range(i+1, n):
            if lst[j] < lst[min_idx]:
                min_idx = j
        lst[i], lst[min_idx] = lst[min_idx], lst[i]
    return lst

Quicksort (recursivo, O(n log n) médio):

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)

Em produção: sorted(lst) ou lst.sort() usam Timsort (híbrido inteligente, O(n log n) garantido).

Complexidade

Notação big-O descreve como o tempo cresce com o tamanho do input:

Notação	Nome	Exemplo
O(1)	Constante	Aceder a índice
O(log n)	Logarítmico	Pesquisa binária
O(n)	Linear	Procurar em lista
O(n log n)	Linearítmico	Mergesort, Timsort
O(n²)	Quadrático	Bubble sort
O(2ⁿ)	Exponencial	Fibonacci ingénuo

Em problemas grandes, escolher algoritmo adequado é mais importante que micro-optimizações.

Módulos e pacotes

Criar módulo próprio

Qualquer ficheiro .py é um módulo.

# math_utils.py
def quadrado(x):
    return x * x

def cubo(x):
    return x ** 3

PI = 3.14159

Usar:

# main.py
import math_utils
print(math_utils.quadrado(5))
print(math_utils.PI)

# ou
from math_utils import quadrado, PI
print(quadrado(5))

Pacotes

Directoria com __init__.py:

projecto/
├── main.py
└── escola/
    ├── __init__.py
    ├── alunos.py
    ├── professores.py
    └── relatorios/
        ├── __init__.py
        └── pdf.py

from escola.alunos import Aluno
from escola.relatorios.pdf import gerar_pdf

__init__.py pode estar vazio ou expor selectivamente:

# escola/__init__.py
from .alunos import Aluno
from .professores import Professor

Permite from escola import Aluno directamente.

pip e ambientes virtuais

pip instala pacotes do PyPI:

pip install requests
pip install pytest
pip install pandas matplotlib

Virtualenv isola dependências por projecto:

python -m venv venv
source venv/bin/activate     # Linux/Mac
venv\Scripts\activate        # Windows
pip install -r requirements.txt

requirements.txt regista dependências:

requests==2.31.0
pytest>=7.0
pandas

Gera-se com pip freeze > requirements.txt.

Dados estruturados

JSON

Formato universal para troca de dados.

import json

# Python → JSON (escrever)
dados = {
    "nome": "Ana",
    "idade": 17,
    "notas": [15, 16, 14],
    "matricula": True
}

texto = json.dumps(dados, indent=2, ensure_ascii=False)
print(texto)

with open("dados.json", "w", encoding="utf-8") as f:
    json.dump(dados, f, indent=2, ensure_ascii=False)

# JSON → Python (ler)
with open("dados.json", encoding="utf-8") as f:
    dados = json.load(f)
print(dados["nome"])

Mapeamento:

Python	JSON
dict	object
list, tuple	array
str	string
int, float	number
True, False	true, false
None	null

CSV

import csv

# Ler como DictReader
with open("alunos.csv", encoding="utf-8") as f:
    reader = csv.DictReader(f)
    for linha in reader:
        print(linha["nome"], linha["nota"])

# Escrever com DictWriter
alunos = [
    {"nome": "Ana", "nota": 17},
    {"nome": "João", "nota": 14}
]
with open("saida.csv", "w", newline="", encoding="utf-8") as f:
    writer = csv.DictWriter(f, fieldnames=["nome", "nota"])
    writer.writeheader()
    writer.writerows(alunos)

newline="" evita linhas em branco no Windows.

APIs REST

Instalar requests:

pip install requests

GET:

import requests

r = requests.get("https://api.github.com/users/torvalds")
if r.status_code == 200:
    dados = r.json()
    print(dados["name"], dados["public_repos"])
else:
    print(f"Erro {r.status_code}")

POST:

r = requests.post(
    "https://api.example.com/users",
    json={"nome": "Ana", "idade": 17},
    headers={"Authorization": "Bearer TOKEN"}
)

Tratamento robusto:

try:
    r = requests.get(url, timeout=5)
    r.raise_for_status()
    dados = r.json()
except requests.Timeout:
    print("Timeout")
except requests.HTTPError as e:
    print(f"Erro HTTP: {e}")
except requests.RequestException as e:
    print(f"Outro erro: {e}")

Testes

Porque testar

Confiança — sabes que o código funciona.
Regressão — mudanças não partem o que já funcionava.
Documentação — testes mostram como usar a função.
Design — código testável é melhor estruturado.

pytest

Instalar:

pip install pytest

Convenções: - Ficheiros: test_*.py ou *_test.py. - Funções: def test_*():.

Exemplo:

# calc.py
def somar(a, b):
    return a + b

def dividir(a, b):
    if b == 0:
        raise ValueError("Divisão por zero")
    return a / b

# test_calc.py
import pytest
from calc import somar, dividir

def test_somar_positivos():
    assert somar(2, 3) == 5

def test_somar_negativos():
    assert somar(-1, -2) == -3

def test_dividir_normal():
    assert dividir(10, 2) == 5

def test_dividir_por_zero():
    with pytest.raises(ValueError):
        dividir(10, 0)

Correr:

pytest
pytest -v              # verbose
pytest test_calc.py    # ficheiro específico
pytest -k "somar"      # filtrar pelo nome

Fixtures

Setup partilhado entre testes:

import pytest

@pytest.fixture
def lista_exemplo():
    return [3, 1, 4, 1, 5, 9, 2, 6]

def test_max(lista_exemplo):
    assert max(lista_exemplo) == 9

def test_min(lista_exemplo):
    assert min(lista_exemplo) == 1

def test_len(lista_exemplo):
    assert len(lista_exemplo) == 8

Cobertura

pytest-cov mede que percentagem do código está coberta por testes:

pip install pytest-cov
pytest --cov=calc

Objectivo razoável: 70-90% nas zonas de lógica. 100% é raro e nem sempre vale a pena.

Boas práticas

Estilo (PEP 8)

snake_case para variáveis e funções.
PascalCase para classes.
MAIÚSCULAS para constantes.
4 espaços de indentação.
Linha até 80-100 caracteres.
Espaços à volta de operadores.

Linter: flake8, pylint, ruff. Formatador: black, ruff format.

Type hints (Python 3.5+)

def somar(a: int, b: int) -> int:
    return a + b

def saudacao(nome: str, lingua: str = "pt") -> str:
    return f"Olá, {nome}!"

Verificador: mypy.

Type hints não afectam execução; servem para documentação e ferramentas.

Docstrings

def calcular_imposto(salario: float, escalao: int) -> float:
    """
    Calcula imposto IRS baseado em salário e escalão.

    Args:
        salario: salário bruto anual em euros.
        escalao: escalão IRS (1-8).

    Returns:
        Imposto a pagar em euros.

    Raises:
        ValueError: se escalão fora de 1-8.
    """
    if not 1 <= escalao <= 8:
        raise ValueError("Escalão tem de estar entre 1 e 8")
    # ...

Gera-se documentação automática com Sphinx, MkDocs, etc.

Logging em vez de print

import logging

logging.basicConfig(level=logging.INFO)
logger = logging.getLogger(__name__)

logger.debug("Detalhe técnico")
logger.info("Operação normal")
logger.warning("Atenção")
logger.error("Erro recuperável")
logger.critical("Erro grave")

Configurável (nível, ficheiro, formato), produção-friendly.

Apêndices

A · Cheatsheet pytest

# Asserções
assert x == y
assert x != y
assert x > y
assert x in lista
assert isinstance(x, int)

# Excepções esperadas
with pytest.raises(ValueError):
    funcao_que_falha()

# Fixtures
@pytest.fixture
def setup():
    return ...

# Parametrizar
@pytest.mark.parametrize("a,b,esperado", [
    (1, 2, 3),
    (5, 5, 10),
])
def test_soma(a, b, esperado):
    assert soma(a, b) == esperado

B · Glossário

API. Application Programming Interface. JSON. JavaScript Object Notation. Pacote. Directoria de módulos Python. pytest. Framework de testes Python. Recursão. Função que se chama a si própria. virtualenv. Ambiente Python isolado.

C · Recursos

docs.python.org/3/tutorial · tutorial oficial.
Real Python · realpython.com.
pytest.org · documentação.
PEP 8 · python.org/dev/peps/pep-0008.