Ficha 01 · Recursão e 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)

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).

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.

Parte II · Pesquisa

Exercício 4 · Pesquisa binária (15 pts)

Implementa pesquisa binária iterativa que devolve o índice do alvo (ou -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?

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):

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?