- 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
Informações dadas (explicitadas):
seq dentro da string texto.”\nInformações dadas (explicitadas):
- Temos duas strings:
textoeseq. - O objetivo é encontrar o índice da primeira ocorrência de
seqdentro detextoe retornar esse índice. - Se
seqnão ocorre dentro detexto, a função deve indicar isso (por exemplo, retornando). - A dica do enunciado diz: elimine o laço
fore acrescente um parâmetro a mais na função. Portanto a versão recursiva deve percorrertextosem 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
em ; se sim, devolva
; se chegar ao fim sem achar, devolva
". O que a recursão faz é exatamente isso, mas sem o e, se não encontrou, chama a si mesma com
.\n
Vamos adicionar um parâmetro a mais chamado na chamada inicial.
texto, verifique se seq começa em
for: ela vai testar a posição corrente
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
Passo 3
Definição dos casos base e das condições importantes (explicação didática):
- Caso especial: se
(isto é, seqé a string vazia), o comportamento comum é retornar(a string vazia ocorre no início de qualquer string). Então: se retornamos . - Caso de não encontrar mais possibilidade: se a posição atual
ié tal que não há caracteres suficientes restantes emtextopara conterseq. Em termos de tamanhos, se, então não é possível encontrar seqcomeçando eminem em posições posteriores — nesse caso retornamos.
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
textoque começa emie tem comprimentocom seq. Em muitas linguagens isso é feito por slicing, por exemplotexto[i:i+len(seq)] == seq. - Se essa comparação for verdadeira, então
seqocorre emi, e devemos retornari.
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):- Se
então retorne . - Se
então retorne (não encontrado). - Se
texto[i:i+len(seq)] == seqentão retornei(encontrou). - Caso contrário, retorne
busca_rec(texto, seq, i+1)(tenta a próxima posição).
- Se
- 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 comi=0, para ficar mais amigável:busca(texto, seq)chamabusca_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
iem. Como não pode crescer indefinidamente (porque logo teremos ), a recursão atinge o caso base onde e retorna , 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
exatamente como o laço faria; se alguma posição corresponde, retorna o primeiro índice, caso contrário retorna .
Passo 7
Complexidade e observações práticas:
- Se
e , cada comparação texto[i:i+m] == seqcusta(no pior caso), e podemos fazer até chamadas recursivas, então o custo total é . - O custo de espaço em recursão é
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".- Chamada inicial:
busca_rec("abcdef", "cde", 0). Testatexto[0:3] == "abc" == "cde"?não. - Chama
busca_rec(..., 1). Testatexto[1:4] == "bcd"? não. - Chama
busca_rec(..., 2). Testatexto[2:5] == "cde"? sim → retorna2. - Resultado final é
2.
- Chamada inicial:
- Exemplo com
seq = ""(vazio): retorna0imediatamente pelo caso especial. - Exemplo onde não existe:
texto = "abc",seq = "d". Chamadas comi=0,1,2falham,i=3faze retorna .
Passo 9
Implementação final (código) — função recursiva com parâmetro a mais
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)
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)
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)