1. Crie a versão recursiva do algoritmo da questão 6 , que retorna o índice de uma sequência seq dentro da string texto. Dica: elimine o laço for e acrescente um parâmetro a mais na função.

Passo 1

O enunciado pede: “Crie a versão recursiva do algoritmo da questão 6, que retorna o índice de uma sequência seq dentro da string texto.”\n
Informações dadas (explicitadas):
  • Temos duas strings: texto e seq.
  • O objetivo é encontrar o índice da primeira ocorrência de seq dentro de texto e retornar esse índice.
  • Se seq não ocorre dentro de texto, a função deve indicar isso (por exemplo, retornando -1).
  • A dica do enunciado diz: elimine o laço for e acrescente um parâmetro a mais na função. Portanto a versão recursiva deve percorrer texto sem usar um laço explícito, usando recursão e um parâmetro extra (normalmente um índice de posição).

Passo 2

Entendendo o que temos que fazer, em palavras simples: imaginar o algoritmo iterativo clássico que faz "para cada posição i em texto, verifique se seq começa em i; se sim, devolva i; se chegar ao fim sem achar, devolva -1". O que a recursão faz é exatamente isso, mas sem o for: ela vai testar a posição corrente i e, se não encontrou, chama a si mesma com i+1.\n
Vamos adicionar um parâmetro a mais chamado i que representa a posição atual em texto que estamos testando. Esse parâmetro começa em 0 na chamada inicial.

Passo 3

Definição dos casos base e das condições importantes (explicação didática):
  • Caso especial: se |\text{seq}| = 0 (isto é, seq é a string vazia), o comportamento comum é retornar 0 (a string vazia ocorre no início de qualquer string). Então: se |\text{seq}| = 0 retornamos 0.
  • Caso de não encontrar mais possibilidade: se a posição atual i é tal que não há caracteres suficientes restantes em texto para conter seq. Em termos de tamanhos, se i + |\text{seq}| > |\text{texto}|, então não é possível encontrar seq começando em i nem em posições posteriores — nesse caso retornamos -1.
    Esses dois são os “casos base” da recursão: condições em que a função não faz chamada recursiva e retorna um resultado direto.

Passo 4

Como verificar se seq ocorre em uma posição i:
  • Simples e direto: comparar o trecho de texto que começa em i e tem comprimento |\text{seq}| com seq. Em muitas linguagens isso é feito por slicing, por exemplo texto[i:i+len(seq)] == seq.
  • Se essa comparação for verdadeira, então seq ocorre em i, e devemos retornar i.
    Essa comparação substitui o laço interno que poderia comparar caracter a caracter; usaremos ela para manter a solução clara e curta (ela é conceitualmente equivalente a comparar manualmente cada caractere).

Passo 5

Esquema recursivo principal (a ideia da chamada recursiva):
  • Função busca_rec(texto, seq, i):
    1. Se |\text{seq}| = 0 então retorne 0.
    2. Se i + |\text{seq}| > |\text{texto}| então retorne -1 (não encontrado).
    3. Se texto[i:i+len(seq)] == seq então retorne i (encontrou).
    4. Caso contrário, retorne busca_rec(texto, seq, i+1) (tenta a próxima posição).
  • A chamada inicial, para o usuário, deverá ser busca_rec(texto, seq, 0). Podemos encapsular numa função com só dois parâmetros que chama internamente o helper com i=0, para ficar mais amigável: busca(texto, seq) chama busca_rec(texto, seq, 0).

Passo 6

Justificativa de terminação e correção (por que isso resolve e não entra em laço infinito):
  • Cada chamada recursiva aumenta o parâmetro i em 1. Como i não pode crescer indefinidamente (porque logo teremos i + |\text{seq}| > |\text{texto}|), a recursão atinge o caso base onde i + |\text{seq}| > |\text{texto}| e retorna -1, ou encontra a sequência e retorna i. Portanto a recursão termina.
  • Correção: a função testa todas as posições possíveis i = 0,1,\dots, |\text{texto}|-|\text{seq}| exatamente como o laço faria; se alguma posição corresponde, retorna o primeiro índice, caso contrário retorna -1.

Passo 7

Complexidade e observações práticas:
  • Se |\text{texto}| = n e |\text{seq}| = m, cada comparação texto[i:i+m] == seq custa O(m) (no pior caso), e podemos fazer até O(n) chamadas recursivas, então o custo total é O(n\cdot m).
  • O custo de espaço em recursão é O(n) no pior caso por causa da profundidade da pilha (uma chamada por posição). Em linguagens sem otimização de cauda, isso pode estourar a pilha para strings muito grandes; para provas de algoritmo isso está OK, só vale saber que é um trade-off versus a versão iterativa.

Passo 8

Exemplo de execução (para sentir o passo a passo):
  • Exemplo: texto = "abcdef", seq = "cde".
    1. Chamada inicial: busca_rec("abcdef", "cde", 0). Testa texto[0:3] == "abc" == "cde"? não.
    2. Chama busca_rec(..., 1). Testa texto[1:4] == "bcd"? não.
    3. Chama busca_rec(..., 2). Testa texto[2:5] == "cde"? sim → retorna 2.
    4. Resultado final é 2.
  • Exemplo com seq = "" (vazio): retorna 0 imediatamente pelo caso especial.
  • Exemplo onde não existe: texto = "abc", seq = "d". Chamadas com i=0,1,2 falham, i=3 faz i + 1 > 3 e retorna -1.

Passo 9

Implementação final (código) — função recursiva com parâmetro a mais i:
def busca_rec(texto, seq, i=0):
if len(seq) == 0:
return 0
if i + len(seq) > len(texto):
return -1
if texto[i:i+len(seq)] == seq:
return i
return busca_rec(texto, seq, i+1)

Resposta

def busca_rec(texto, seq, i=0):
if len(seq) == 0:
return 0
if i + len(seq) > len(texto):
return -1
if texto[i:i+len(seq)] == seq:
return i
return busca_rec(texto, seq, i+1)