Escreva uma função recursiva que determina se os elementos de um vetor v formam um palíndromo. Note, por exemplo, que:
  • se v é igual a [1,10,40,10,1], então v é um palíndromo e
  • se v é igual a [20,50,31,20], então v não é um palíndromo.

Passo 1

O enunciado pede uma função recursiva que verifica se os elementos de um vetor v formam um palíndromo. Especificamente:
  • Entrada: um vetor v de elementos (por exemplo inteiros).
  • Saída: um valor booleano indicando se v é palíndromo (verdadeiro) ou não (falso).
Exemplos dados:
  • v = [1,10,40,10,1] deve resultar em verdadeiro (é palíndromo).
  • v = [20,50,31,20] 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 v é 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 i desde o início até a metade vale:
v[i] = v[n-1-i],
onde n é o tamanho do vetor.
Intuição recursiva simples: para decidir se v é 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 \text{pal}(v,i,j)\) a propriedade "o subvetor de \(v\) entre os índices \(i\) e \(j\) (inclusive) é palíndromo". Então: \[\text{pal}(v,i,j) = \begin{cases} \text{True}, & \text{se } i \ge j,\\[4pt] \text{False}, & \text{se } v[i] \neq v[j],\\[4pt] \text{pal}(v,i+1,j-1), & \text{caso contrário.} \end{cases}
Explicação das três linhas:
  • Se i \ge j\]: subvetor vazio (\(i>j) ou um único elemento ( i=j) — ambos são palíndromos por definição (casos base).
  • Se v[i] \neq v[j]: 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 i (início) e j (fim) que delimitam a janela atual dentro de v. Assim não há cópia de dados, apenas passagem de índices na pilha de chamadas.
Parâmetros da função que vou usar:
  • v: o vetor original.
  • i: índice do elemento atual do início (inicialmente 0).
  • j: índice do elemento atual do fim (inicialmente \text{len}(v)-1).

Passo 5

Escrevendo o algoritmo em pseudocódigo (passo a passo, como escrever na prova):
  1. Se i \ge j então retornar Verdadeiro. (caso base)
  2. Se v[i] \neq v[j] então retornar Falso. (caso de falha)
  3. Caso contrário, retornar o resultado de \text{pal}(v,i+1,j-1). (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)
Explicando cada linha:
  • if j is None: j = len(v) - 1 — inicializa o índice final na primeira chamada, permitindo que o examinador chame apenas is_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 ( i aumenta, j diminui), portanto a distância j-i diminui estritamente; eventualmente i \ge j e alcança o caso base.
  • Correção (intuitiva por indução): para janela de tamanho 0 ou 1 a função retorna True (base). Se a função está correta para todas janelas de tamanho menor que k, então para janela de tamanho k a função compara extremidades; se diferentes retorna False (correto); se iguais reduz para subjanela de tamanho k-2 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 \lceil n/2\rceil comparações — complexidade de tempo O(n), onde n= len (v).
  • Espaço (pilha de chamadas): a profundidade máxima de recursão é \lceil n/2\rceil, logo uso de pilha O(n) 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: v=[1,10,40,10,1]. Chamadas e comparações:
  • \text{pal}(v,0,4): compara v[0]=1 com v[4]=1 (iguais) → chama \text{pal}(v,1,3).
  • \text{pal}(v,1,3): compara v[1]=10 com v[3]=10 (iguais) → chama \text{pal}(v,2,2).
  • \text{pal}(v,2,2): aqui i=j → retorna True.
    Retorna True até o topo → vetor é palíndromo.
Exemplo 2: v=[20,50,31,20]. Chamadas e comparações:
  • \text{pal}(v,0,3): compara v[0]=20 com v[3]=20 (iguais) → chama \text{pal}(v,1,2).
  • \text{pal}(v,1,2): compara v[1]=50 com v[2]=31 (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: i \ge j → True; v[i] \neq v[j] → False.
  • Mostre a chamada recursiva \text{pal}(v,i+1,j-1).
  • Comente a complexidade O(n) e o custo de pilha O(n).
  • 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)

Exercícios relacionados