Escreva uma função recursiva que determina se os elementos de um vetor
formam um palíndromo. Note, por exemplo, que:
- se
é igual a
, então
é um palíndromo e
- se
é igual a
, então
não é um palíndromo.
Passo 1
O enunciado pede uma função recursiva que verifica se os elementos de um vetor
formam um palíndromo. Especificamente:
- Entrada: um vetor
de elementos (por exemplo inteiros). - Saída: um valor booleano indicando se
é palíndromo (verdadeiro) ou não (falso).
Exemplos dados:
-
deve resultar em verdadeiro (é palíndromo). -
deve resultar em falso (não é palíndromo).
Informações relevantes fornecidas:
- Deve ser usada uma solução recursiva.
- Não há restrição explícita sobre linguagem; a função deve testar igualdade entre elementos simetricamente colocados no vetor.
Passo 2
O que é um palíndromo, de forma operacional?
Um vetor é palíndromo se o primeiro elemento é igual ao último, o segundo é igual ao penúltimo, e assim sucessivamente até o meio. Formalmente, usando índices, para todos os índices
desde o início até a metade vale:
Um vetor
onde
é o tamanho do vetor.
Intuição recursiva simples: para decidir se
é palíndromo,
- compare o elemento na posição inicial com o da posição final;
- se forem diferentes, já sabemos que não é palíndromo;
- se forem iguais, o problema reduz-se a verificar se o subvetor que exclui esses dois elementos é palíndromo.
Passo 3
Definição recursiva (forma matemática da recorrência). Seja
Explicação das três linhas:
- Se
) ou um único elemento (
) — ambos são palíndromos por definição (casos base). - Se
: encontrou-se um par simétrico desigual — não é palíndromo. - Caso contrário: remover as duas extremidades e aplicar recursão ao subproblema.]
Passo 4
Decisão de implementação (por que usar índices):
- Uma abordagem recursiva ingênua poderia criar cópias do subvetor em cada chamada (por exemplo usando slices). Isso funciona, mas tem custo extra de tempo e memória (cada slice copia elementos).
- Melhor usar dois índices
(início) e (fim) que delimitam a janela atual dentro de . Assim não há cópia de dados, apenas passagem de índices na pilha de chamadas.
Parâmetros da função que vou usar:
-
: o vetor original. -
: índice do elemento atual do início (inicialmente ). -
: índice do elemento atual do fim (inicialmente ).
Passo 5
Escrevendo o algoritmo em pseudocódigo (passo a passo, como escrever na prova):
- Se
então retornar Verdadeiro. (caso base) - Se
então retornar Falso. (caso de falha) - Caso contrário, retornar o resultado de
. (chamada recursiva)
Em palavras: “Se a janela atual tem 0 ou 1 elemento, é palíndromo. Se as extremidades diferem, não é. Senão, avance uma posição em cada extremidade e repita.”
Passo 6
Implementação prática em Python (linha a linha explicada). A função abaixo é exatamente a versão que você pode escrever numa prova/programa:
def is_palindrome(v, i=0, j=None):
if j is None:
j = len(v) - 1
if i >= j:
return True
if v[i] != v[j]:
return False
return is_palindrome(v, i+1, j-1)
if j is None:
j = len(v) - 1
if i >= j:
return True
if v[i] != v[j]:
return False
return is_palindrome(v, i+1, j-1)
Explicando cada linha:
if j is None: j = len(v) - 1— inicializa o índice final na primeira chamada, permitindo que o examinador chame apenasis_palindrome(v).if i >= j: return True— caso base: subvetor vazio ou de um elemento.if v[i] != v[j]: return False— se as extremidades diferem, podemos terminar cedo.return is_palindrome(v, i+1, j-1)— chamada recursiva reduzindo a janela.
Observação prática para prova: se quiser, pode escrever uma função wrapper
is_palindrome(v) que chama uma função auxiliar recursiva com os índices explicitamente, para ficar mais claro.Passo 7
Por que a recursão termina e está correta?
- Terminação: em cada chamada recursiva os índices avançam (
aumenta, diminui), portanto a distância diminui estritamente; eventualmente e alcança o caso base. - Correção (intuitiva por indução): para janela de tamanho
ou a função retorna True (base). Se a função está correta para todas janelas de tamanho menor que , então para janela de tamanho a função compara extremidades; se diferentes retorna False (correto); se iguais reduz para subjanela de tamanho que, por hipótese de indução, é corretamente detectada. Logo funciona.
Passo 8
Complexidade e observações de desempenho:
- Tempo: cada chamada compara um par de elementos e avança dois índices, portanto no máximo
comparações — complexidade de tempo , onde len . - Espaço (pilha de chamadas): a profundidade máxima de recursão é
, logo uso de pilha no pior caso. Se o ambiente não tolera recursão profunda, usar versão iterativa (dois índices em loop) evita a pilha.
Passo 9
Traço da execução nos exemplos (mostra o que acontece na recursão):
Exemplo 1:
. Chamadas e comparações:
-
: compara com (iguais) → chama . -
: compara com (iguais) → chama . -
: aqui → retorna True.
Retorna True até o topo → vetor é palíndromo.
Exemplo 2:
. Chamadas e comparações:
-
: compara com (iguais) → chama . -
: compara com (diferentes) → retorna False.
Retorna False até o topo → vetor não é palíndromo.
Passo 10
Dicas rápidas para a prova (o que anotar se pedir a função recursiva):
- Declare claramente os casos base:
→ True; → False. - Mostre a chamada recursiva
. - Comente a complexidade
e o custo de pilha . - Se houver restrição de memória, proponha a versão iterativa com dois índices em loop.
Resposta
def is_palindrome(v, i=0, j=None):
if j is None:
j = len(v) - 1
if i >= j:
return True
if v[i] != v[j]:
return False
return is_palindrome(v, i+1, j-1)
if j is None:
j = len(v) - 1
if i >= j:
return True
if v[i] != v[j]:
return False
return is_palindrome(v, i+1, j-1)