Python

EXERCÍCIO 01

Análise de Função Recursiva

Identificar o caso base de uma função recursiva que imprime números pares.

▼

Enunciado: O código abaixo define uma função recursiva que recebe 2 números inteiros em parâmetros chamados "inicio" e "fim”. A função imprime número sim, número não, na faixa de "inicio" até "fim". Por exemplo, se "inicio" for 0 e "fim" for 10, a função deve imprimir 0, 2, 4, 6, 8 e 10. Identifique o caso base dessa recursão, justificando sua resposta.

                    def imprime_pulando(inicio, fim):

                      if inicio <= fim:

                        print(inicio)

                        imprime_pulando(inicio + 2, fim)

Toda função recursiva precisa de um caso base, isto é, uma condição que diga: "pare por aqui, não continue chamando a si mesma". No exemplo, temos:

                    if inicio <= fim:
                        print(inicio)
                        imprime_pulando(inicio + 2, fim)

👉 Repare que a chamada recursiva só acontece se inicio <= fim. Isso significa que o programa continua "pulando de 2 em 2" enquanto a condição for verdadeira. Quando inicio fica maior que fim, o if não executa: - nada é impresso, - não há nova chamada recursiva, - e a função "volta" encerrando a cadeia. Ou seja, o caso base implícito é inicio > fim. Esse é o ponto em que a recursão termina naturalmente.

EXERCÍCIO 02

Correção de Função Recursiva

Adicionar o caso base a uma função de soma recursiva para evitar loop infinito.

▼

Enunciado: O código abaixo define uma função que deveria retornar a soma de todos os números inteiros na faixa de "inicio" até "fim". Entretanto, está faltando o caso base no código, e ele executará indefinidamente! Corrija o código adicionando o caso base correto.

# Código Original (com erro)
def soma(inicio, fim):
  return fim + soma(inicio, fim - 1)

# Código Corrigido
def soma_corrigida(inicio, fim):
  # Caso base: se o fim chegar ao início, retorna o próprio número.
  if fim == inicio:
    return inicio
  # Passo recursivo: soma o número atual com a soma do resto do intervalo.
  return fim + soma_corrigida(inicio, fim - 1)

print(soma_corrigida(1, 10))55

A recursão precisa de uma condição de parada. A função original chama a si mesma com `fim - 1`, diminuindo o valor de `fim` a cada passo. O caso base lógico é quando `fim` se torna igual a `inicio`. Nesse ponto, a soma para, retornando o último valor e permitindo que a cadeia de somas seja calculada corretamente.

EXERCÍCIO 03

Contagem de Caracteres Recursiva

Criar uma função recursiva para contar o total de caracteres em um array de strings.

▼

Enunciado: Escreva uma função recursiva que recebe um array de strings e retorna o nº total de caracteres em todas as strings.

def contar_caracteres(arr):
  # Caso base: se o array estiver vazio, não há caracteres.
  if not arr:
    return 0
  # Passo recursivo: conta os caracteres da primeira string
  # e soma com a contagem do resto do array.
  return len(arr[0]) + contar_caracteres(arr[1:])

print(contar_caracteres(["ab", "c", "def", "ghij"]))10

Lógica: A função resolve o problema "quebrando-o" em partes menores. Ela calcula o comprimento da primeira string (`len(arr[0])`) e delega o resto do trabalho (`arr[1:]`, que é o array sem o primeiro elemento) para a próxima chamada recursiva. O caso base `if not arr:` garante que a recursão pare quando o array se esvaziar.

EXERCÍCIO 04

Filtragem de Pares Recursiva

Criar uma função recursiva para filtrar números pares de um array.

▼

Enunciado: Escreva uma função recursiva que recebe um array de números inteiros e retorna um novo array contendo apenas os números pares.

def filtra_pares(arr):
  # Caso base: array vazio retorna array vazio.
  if not arr:
    return []
  # Pega o primeiro número e o resto do array.
  primeiro = arr[0]
  resto = arr[1:]
  # Chama a função para o resto do array.
  pares_do_resto = filtra_pares(resto)

  # Se o primeiro número for par, adiciona ele ao resultado.
  if primeiro % 2 == 0:
    return [primeiro] + pares_do_resto
  # Senão, retorna apenas o resultado do resto.
  else:
    return pares_do_resto

print(filtra_pares([1, 2, 3, 4, 5, 6, 7, 8]))[2, 4, 6, 8]

EXERCÍCIO 05

Busca de Caractere Recursiva

Encontrar o primeiro índice do caractere 'x' em uma string usando recursão.

▼

Enunciado: Escreva uma função recursiva que recebe uma string e retorna o 1º índice que contém o caractere 'x'. Caso a string não contenha 'x', a função deve retornar -1.

def encontrar_x(s, indice=0):
  # Caso base 1: Se o índice atual ultrapassar o tamanho da string, 'x' não foi encontrado.
  if indice >= len(s):
    return -1
  # Caso base 2: Se o caractere no índice atual for 'x', retorna o índice.
  if s[indice] == 'x':
    return indice
  # Passo recursivo: chama a função para o próximo índice.
  return encontrar_x(s, indice + 1)

print(encontrar_x("abcdefghijklmnopqrstuvwxyz"))23
print(encontrar_x("abcde"))-1

EXERCÍCIO 06

Busca de Arquivos por Nome

Criar um script que busca recursivamente arquivos em um diretório por um nome.

▼

Enunciado: Escreva um programa que receba como argumento de linha de comando uma string e imprima o caminho de todos os arquivos existentes no diretório corrente (incluindo os arquivos dos subdiretórios) cujos nomes incluam a string de entrada.

                    import os

                    import sys

                    def encontrar_arquivos(diretorio, termo_busca):

                      # os.walk percorre a árvore de diretórios de cima para baixo.

                      for raiz, dirs, arquivos in os.walk(diretorio):

                        for nome_arquivo in arquivos:

                          # Verifica se o termo de busca está no nome do arquivo.

                          if termo_busca in nome_arquivo:

                            # os.path.join monta o caminho completo do arquivo.

                            print(os.path.join(raiz, nome_arquivo))

                    if __name__ == "__main__":

                      if len(sys.argv) != 2:

                        print("Uso: python nome_do_script.py ")

                        sys.exit(1)

                      termo = sys.argv[1]

                      diretorio_atual = '.' # '.' representa o diretório corrente

                      encontrar_arquivos(diretorio_atual, termo)

Como usar: Salve o código como `buscar.py`. Para procurar todos os arquivos que contenham "html" no nome, execute no terminal: `python buscar.py html`. A função `os.walk` é a ferramenta ideal para varrer diretórios de forma recursiva.

EXERCÍCIO 07

Função de Potência Recursiva

Implementar uma função recursiva para calcular potências, incluindo expoentes negativos.

▼

Enunciado: Escreva uma função recursiva chamada "potencia" para elevar um nº a uma potência. Ela deverá ter 2 parâmetros: base (int ou float) e expoente (int). Teste sua função com várias combinações, incluindo expoentes positivos e negativos, além dos casos especiais em que o expoente é 0 ou 1.

def potencia(base, expoente):
  # Caso especial: expoente negativo.
  if expoente < 0:
    return 1 / potencia(base, -expoente)
  # Caso base: qualquer número elevado a 0 é 1.
  if expoente == 0:
    return 1
  # Caso base: qualquer número elevado a 1 é ele mesmo.
  if expoente == 1:
    return base
  # Passo recursivo: base * base^(expoente-1)
  return base * potencia(base, expoente - 1)

print(f"2^3 = {potencia(2, 3)}")2^3 = 8
print(f"5^0 = {potencia(5, 0)}")5^0 = 1
print(f"2^-3 = {potencia(2, -3)}")2^-3 = 0.125

EXERCÍCIO 08

Impressão de Lista Aninhada

Criar uma função recursiva para imprimir todos os números de uma lista com múltiplos níveis de aninhamento.

▼

Enunciado: Escreva uma função recursiva chamada "imprime_numeros" que receba uma lista contendo tanto números quanto outras listas (aninhadas) e imprima todos os números existentes na lista, um por um.

def imprime_numeros(lista):
  for item in lista:
    # Se o item for uma lista, chama a função recursivamente para ela.
    if isinstance(item, list):
      imprime_numeros(item)
    # Se for um número, imprime.
    else:
      print(item)

lista_aninhada = [1, 2, [3, 4, [5, 6]], 7]
imprime_numeros(lista_aninhada)1
2
3
4
5
6
7

EXERCÍCIO 09

Otimização de Função Recursiva

Corrigir uma função recursiva para eliminar chamadas desnecessárias.

▼

Enunciado: O código abaixo define uma função recursiva que retorna a soma dos números de uma lista a partir de um índice inicial, ignorando números que fariam a soma ultrapassar 100. Corrija o código para eliminar as chamadas recursivas desnecessárias.

# Código Corrigido
def soma_ate_100_corrigida(lista, inicio=0):
  # Caso base: se o índice ultrapassar o limite da lista, a soma é 0.
  if inicio >= len(lista):
    return 0

  # Calcula a soma do resto da lista UMA VEZ e armazena.
  soma_do_resto = soma_ate_100_corrigida(lista, inicio + 1)

  # Verifica se o número atual estoura o limite.
  if lista[inicio] + soma_do_resto > 100:
    return soma_do_resto
  else:
    return lista[inicio] + soma_do_resto

print(soma_ate_100_corrigida([10, 20, 70, 5, 5]))95

Problema Original: A função original chamava `soma_ate_100` duas vezes em alguns casos, uma para o teste `if` e outra para o `return`. Isso é ineficiente. Solução: A versão corrigida chama a função recursiva apenas uma vez por nível, armazena o resultado em `soma_do_resto` e reutiliza essa variável, evitando o recálculo.

EXERCÍCIO 10

Análise de Complexidade (Big O)

Descrever a complexidade da função `soma_ate_100_corrigida`.

▼

Enunciado: Use a notação Big O para descrever a complexidade da função "soma_ate_100" corrigida que você implementou na questão anterior, justificando sua resposta.

Resposta: A complexidade de tempo da função `soma_ate_100_corrigida` é O(N), onde N é o número de elementos na lista.

Justificativa: A função faz uma única chamada recursiva para cada elemento da lista, do final até o início. Em cada chamada, ela realiza um número constante de operações (uma comparação, uma soma, um `return`). Como a função é chamada N vezes e o trabalho em cada chamada é constante, o tempo de execução total cresce linearmente com o tamanho da lista.

EXERCÍCIO 11

Otimização com Memoização

Reescrever a função da sequência de Golomb usando memoização para otimizá-la.

▼

Enunciado: O código abaixo define uma função recursiva que calcula o N-ésimo número de uma sequência matemática conhecida como sequência de Golomb. Entretanto, ela é terrivelmente ineficiente! Reescreva a função usando memoização para otimizá-la.

                    memo = {} # Dicionário para armazenar resultados já calculados

                    def golomb_memo(n):

                      # Se o resultado já foi calculado, retorna do cache.

                      if n in memo:

                        return memo[n]

                      # Caso base.

                      if n == 1:

                        return 1

                      # Calcula o resultado.

                      resultado = 1 + golomb_memo(n - golomb_memo(golomb_memo(n - 1)))

                      # Armazena no cache antes de retornar.

                      memo[n] = resultado

                      return resultado

                    print(golomb_memo(20))

Memoização: É uma técnica de otimização que armazena os resultados de chamadas de função caras e retorna o resultado em cache quando as mesmas entradas ocorrem novamente. A função original recalculava os mesmos valores de `golomb` várias vezes. Com a memoização, cada valor é calculado apenas uma vez, tornando a execução drasticamente mais rápida.

EXERCÍCIO 12

Caminhos Únicos com Memoização

Otimizar a função recursiva de "caminhos únicos" com memoização.

▼

Enunciado: No problema dos "caminhos únicos", queremos calcular o nº de diferentes caminhos mais curtos possíveis do canto superior esquerdo até o canto inferior direito de um grid. Reescreva a função recursiva abaixo usando memoização para melhorar sua eficiência.

memo_caminhos = {}

def caminhos_unicos_memo(linhas, colunas):
  # Usa uma tupla (linhas, colunas) como chave do cache.
  if (linhas, colunas) in memo_caminhos:
    return memo_caminhos[(linhas, colunas)]
  # Caso base: se estiver na primeira linha ou coluna, só há 1 caminho.
  if linhas == 1 or colunas == 1:
    return 1

  # Calcula o resultado.
  resultado = caminhos_unicos_memo(linhas - 1, colunas) + caminhos_unicos_memo(linhas, colunas - 1)

  # Armazena no cache.
  memo_caminhos[(linhas, colunas)] = resultado
  return resultado

print(caminhos_unicos_memo(3, 7))28

EXERCÍCIO 13

Caminhos Únicos com DP Bottom-Up

Reescrever a função de "caminhos únicos" usando programação dinâmica bottom-up.

▼

Enunciado: Reescreva a função da questão anterior, desta vez usando programação dinâmica bottom-up para melhorar sua eficiência.

def caminhos_unicos_dp(linhas, colunas):
  # Cria um grid (matriz) para armazenar os resultados parciais.
  grid = [[0 for _ in range(colunas)] for _ in range(linhas)]

  # Preenche a primeira linha e a primeira coluna com 1.
  for i in range(linhas): grid[i][0] = 1
  for j in range(colunas): grid[0][j] = 1

  # Preenche o resto do grid.
  for i in range(1, linhas):
    for j in range(1, colunas):
      grid[i][j] = grid[i-1][j] + grid[i][j-1]

  # O resultado final está no canto inferior direito.
  return grid[linhas-1][colunas-1]

print(caminhos_unicos_dp(3, 7))28

Bottom-Up vs. Memoização: A memoização (Top-Down) resolve o problema de cima para baixo, usando recursão e cache. A programação dinâmica Bottom-Up resolve de baixo para cima, preenchendo uma tabela de resultados de forma iterativa, sem recursão. Geralmente, a abordagem Bottom-Up é mais eficiente em termos de uso de memória de pilha.

EXERCÍCIO 14

Maior Produto de Três Números

Encontrar o maior produto de três números em um array com complexidade O(N log N).

▼

Enunciado: Escreva uma função que recebe um array de números positivos e retorna o maior produto de quaisquer 3 números do array. Sua função deve ter complexidade O(N log N).

def maior_produto_de_tres(arr):
  # Ordenar o array custa O(N log N).
  arr.sort()
  n = len(arr)

  # O maior produto pode ser de dois tipos:
  # 1. O produto dos três maiores números (todos positivos).
  produto1 = arr[n-1] * arr[n-2] * arr[n-3]

  # 2. O produto dos dois menores números (que podem ser negativos)
  #    com o maior número. (Dois negativos resultam em um positivo).
  produto2 = arr[0] * arr[1] * arr[n-1]

  return max(produto1, produto2)

print(maior_produto_de_tres([-10, -10, 5, 2]))500

EXERCÍCIO 15

Ordenação de Cores com Quicksort

Implementar Quicksort para ordenar uma lista de dicionários de cores por R, G e B.

▼

Enunciado: Desenvolva uma função que implemente o algoritmo quicksort para ordenar uma lista de cores (dicionários) usando os seguintes critérios: (1) ordem crescente de R; (2) em caso de empate, ordem crescente de G; (3) em caso de empate, ordem crescente de B.

                    def quicksort_cores(lista_cores):

                      if len(lista_cores) < 2:

                        return lista_cores

                      pivo = lista_cores[0]

                      menores = []

                      maiores = []

                      for cor in lista_cores[1:]:

                        # Compara usando uma tupla para garantir a ordem dos critérios.

                        if (cor['r'], cor['g'], cor['b']) < (pivo['r'], pivo['g'], pivo['b']):

                          menores.append(cor)

                        else:

                          maiores.append(cor)

                      return quicksort_cores(menores) + [pivo] + quicksort_cores(maiores)

EXERCÍCIO 16

Seleção de Candidatos com Quickselect

Implementar Quickselect para encontrar os K melhores candidatos em um processo seletivo.

▼

Enunciado: Desenvolva uma função que implemente o algoritmo quickselect para encontrar e retornar os K primeiros colocados em um processo seletivo. Critérios: (1) maior pontuação; (2) em caso de empate, maior idade.

                    import random

                    def quickselect_candidatos(candidatos, k):

                      if not candidatos or k <= 0:

                        return []

                      # Escolhe um pivô aleatório.

                      pivo = random.choice(candidatos)

                      pivo_crit = (-pivo['pontos'], -pivo['idade']) # Negativo para ordenar decrescente

                      # Particiona a lista em menores, iguais e maiores que o pivô.

                      menores, iguais, maiores = [], [], []

                      for c in candidatos:

                        c_crit = (-c['pontos'], -c['idade'])

                        if c_crit < pivo_crit: menores.append(c)

                        elif c_crit == pivo_crit: iguais.append(c)

                        else: maiores.append(c)

                      # Decide qual partição explorar recursivamente.

                      if k <= len(menores):

                        return quickselect_candidatos(menores, k)

                      elif k <= len(menores) + len(iguais):

                        return menores + iguais[:k - len(menores)]

                      else:

                        return menores + iguais + quickselect_candidatos(maiores, k - len(menores) - len(iguais))