Aula 8.2 - Funções: Recursão e Validação

♻️ 8.2 Funções Recursivas

Uma função é recursiva quando ela chama a si mesma. Para evitar um loop infinito, toda função recursiva precisa de um caso base — uma condição que encerra a recursão sem fazer nova chamada.

O fatorial é o exemplo clássico: fat(n) = n × fat(n-1), e fat(1) = 1 (caso base).

Listagem 8.11 — Fatorial recursivodef fatorial(n):
    if n <= 1:
        return 1
    return n * fatorial(n - 1)

print(fatorial(5))   # 120

Rastreando a execução

Podemos adicionar um print para visualizar a pilha de chamadas:

Listagem 8.12 — Fatorial com rastreamentodef fatorial(n):
    print(f"fatorial({n})")
    if n <= 1:
        return 1
    return n * fatorial(n - 1)

fatorial(4)

Listagem 8.13 — Saída do rastreamentofatorial(4)
fatorial(3)
fatorial(2)
fatorial(1)

Cada chamada fica “suspensa” esperando o resultado da próxima, formando uma pilha de chamadas. Quando o caso base é atingido, os retornos se propagam:

fatorial(4) → 4 × fatorial(3) fatorial(3) → 3 × fatorial(2) fatorial(2) → 2 × fatorial(1) fatorial(1) → 1 (caso base) ← 2 × 1 = 2 ← 3 × 2 = 6 ← 4 × 6 = 24

💡 Toda função recursiva precisa de: (1) um caso base que encerra a recursão e (2) uma chamada recursiva que aproxima o problema do caso base.

🐀 Sequência de Fibonacci

A sequência de Fibonacci é definida como: F(0) = 0, F(1) = 1 e F(n) = F(n-1) + F(n-2) para n ≥ 2. A sequência é: 0, 1, 1, 2, 3, 5, 8, 13, 21, …

Listagem 8.14 — Fibonacci recursivodef fibonacci(n):
    if n <= 1:
        return n
    return fibonacci(n - 1) + fibonacci(n - 2)

for i in range(10):
    print(fibonacci(i), end=" ")

0 1 1 2 3 5 8 13 21 34

Note que a recursão do Fibonacci faz duas chamadas recursivas, tornando o algoritmo exponencial. Para valores grandes de n, prefira a versão iterativa.

✏️ Exercício 8.7

Escreva uma função recursiva mdc(a, b) que calcule o Máximo Divisor Comum usando o algoritmo de Euclides: mdc(a, b) = mdc(b, a % b), caso base: mdc(a, 0) = a.

✏️ Exercício 8.8

Escreva uma função mmc(a, b) que calcule o Mínimo Múltiplo Comum usando a relação: mmc(a, b) = a * b // mdc(a, b).

✏️ Exercício 8.9

Escreva uma função recursiva soma_digitos(n) que retorne a soma dos dígitos de um número inteiro positivo. Por exemplo: soma_digitos(1234) == 10.

✏️ Exercício 8.10

Escreva uma função recursiva potencia(base, exp) que calcule base elevado a exp sem usar o operador **.

✅ 8.3 Validação de Entrada

Programas robustos precisam validar os dados fornecidos pelo usuário. Sem funções, o código de validação fica repetido em vários lugares:

Listagem 8.15 — Validação sem função (repetição de código)# Lendo a idade
while True:
    idade = int(input("Idade (0-120): "))
    if 0 <= idade <= 120:
        break
    print("Digite um valor entre 0 e 120.")

# Lendo a nota
while True:
    nota = int(input("Nota (0-10): "))
    if 0 <= nota <= 10:
        break
    print("Digite um valor entre 0 e 10.")

Com uma função de validação genérica, o código fica muito mais limpo:

Listagem 8.16 — Função faixa_intdef faixa_int(msg, minimo, maximo):
    while True:
        n = int(input(msg))
        if minimo <= n <= maximo:
            return n
        print(f"Digite um valor entre {minimo} e {maximo}.")

# Uso da função
idade = faixa_int("Idade (0-120): ", 0, 120)
nota  = faixa_int("Nota (0-10): ", 0, 10)

💡 Funções de validação eliminam a duplicação de código e centralizam a lógica de verificação. Se a regra muda, basta alterar em um único lugar.

✏️ Exercício 8.11

Crie uma função faixa_float(msg, minimo, maximo) similar a faixa_int, porém para números reais. Use-a para ler peso (30.0 a 300.0) e altura (0.5 a 2.5).

✏️ Exercício 8.12

Crie uma função le_opcao(msg, opcoes) que exiba uma mensagem e aceite apenas uma das strings contidas na lista opcoes. Por exemplo: le_opcao("S ou N? ", ["S", "N"]).

♻️ Recursão e Validação