Escreva uma função recursiva que recebe um número inteiro positivo n, um vetor v contendo n números inteiros e verifica se este vetor está ordenado crescentemente. Esta função deve devolver os valores 1 e 0 , indicando, respectivamente, se v está ou não ordenado.

Passo 1

O enunciado pede: escrever uma função recursiva que recebe um inteiro positivo n e um vetor v com n inteiros e verifica se o vetor está ordenado crescentemente. A função deve devolver 1 se v está ordenado e 0 caso contrário.
Informações relevantes dadas:
  • Entrada: um inteiro positivo n (ou seja, n\ge 1) e um vetor v com n inteiros.
  • Saída esperada: valor inteiro 1 (verdadeiro) se o vetor estiver ordenado crescentemente, ou 0 (falso) caso não esteja.
  • Interpretação adotada aqui para “ordenado crescentemente”: cada elemento é menor ou igual ao próximo, isto é, para todo índice i válido vale v[i]\le v[i+1]. (Se o professor exigir estritamente crescente, troque \le por <.)
O que a função precisa fazer, em termos claros:
  • Verificar se para todos i com 0\le i\le n-2 tem-se v[i]\le v[i+1].
  • Fazer isso usando recursão (sem usar laços explícitos para a verificação principal).

Passo 2

Ideia recursiva simples e natural:
  • Base da recursão: um vetor de tamanho 1 (ou 0) está trivialmente ordenado. Então se n\le 1 devolvemos 1.
  • Passo recursivo: para n\ge 2 podemos comparar os dois últimos elementos v[n-2] e v[n-1].
    • Se v[n-2]>v[n-1], então há uma violação da ordenação e devolvemos 0.
    • Caso contrário, os dois últimos estão em ordem relativa; a ordenação do vetor inteiro depende de os primeiros n-1 elementos estarem ordenados. Então chamamos recursivamente a função em n-1.
  • Recorrendo dessa forma, cada chamada reduz n em 1 até atingir a base n=1.
Por que essa escolha é boa:
  • É simples de entender e implementar.
  • Cada chamada faz apenas uma comparação e chama recursivamente para um tamanho menor, o que leva a uma solução clara e direta.

Passo 3

Escrever a recursão em forma de pseudocódigo e explicar cada linha:
Pseudocódigo (comentado):
  • Função ordenado( n, v):
    1. Se n\le 1 então retornar 1. (Base: vetor unitário é ordenado.)
    2. Se v[n-2] > v[n-1] então retornar 0. (Encontrou inversão.)
    3. Caso contrário, retornar ordenado( n-1, v). (Verifica o prefixo de tamanho n-1.)
Explicação detalhada de cada passo:
  • Linha 1 (base): quando n=1 não existem pares para comparar, logo o vetor está ordenado.
  • Linha 2: comparar os elementos nas posições n-2 e n-1 é suficiente para detectar se a última transição viola a ordenação.
  • Linha 3: se essa transição está ok, resta verificar se o prefixo de tamanho n-1 também está ordenado; a recursão faz exatamente isso.
Observação sobre índices: estou usando índice baseado em zero (como em C/Pascal/C++/Java), onde elementos vão de v[0] até v[n-1].

Passo 4

Prova intuitiva de correção por indução (para aumentar confiança, útil na prova):
  • Caso base: para n=1 a função retorna 1; isso é correto porque um único elemento está ordenado.
  • Passo indutivo: suponha que para todo k<n a função retorna 1 se e somente se os primeiros k elementos estão ordenados. Para n:
    • Se v[n-2]>v[n-1], a função retorna 0 e isso é correto (há uma inversão).
    • Se v[n-2]\le v[n-1], a função retorna o resultado de ordenado( n-1, v). Pelo passo indutivo, essa chamada devolve 1 sse os primeiros n-1 elementos estão ordenados. Como também temos v[n-2]\le v[n-1], conclui-se que todos os pares consecutivos entre 0 e n-2 estão em ordem, logo todo o vetor de tamanho n está em ordem. Assim a função retorna 1 exatamente quando o vetor de tamanho n está ordenado. Isso fecha a indução.

Passo 5

Complexidade e limitações práticas:
  • Tempo: cada chamada faz uma comparação e, no pior caso, faz n-1 chamadas recursivas; portanto o tempo é O(n).
  • Espaço (recursão): a profundidade de recursão é O(n), portanto utiliza-se O(n) espaço de pilha. Se o compilador/linguagem suportar otimização de tail-call (no caso de uma versão tail-recursiva) isso poderia ficar em O(1), mas a versão apresentada aqui, dependendo da linguagem, pode não ser otimizada e usar pilha linear.
  • Caso prático: para vetores muito grandes em linguagens que não otimizam tail recursion, pode-se preferir uma versão iterativa para evitar estouro de pilha.

Passo 6

Exemplo passo-a-passo (um walkthrough para fixar a intuição):
Exemplo 1 (ordenado): v=[1,2,2,5], n=4.
  • Chamada ordenado(4,v): compara v[2]=2 com v[3]=5 2\le5 → chama ordenado(3,v).
  • Chamada ordenado(3,v): compara v[1]=2 com v[2]=2 2\le2 → chama ordenado(2,v).
  • Chamada ordenado(2,v): compara v[0]=1 com v[1]=2 1\le2 → chama ordenado(1,v).
  • Chamada ordenado(1,v): n\le1 retorna 1. Todas as chamadas retornam 1.
Exemplo 2 (não ordenado): v=[1,4,3,5], n=4.
  • ordenado(4,v): compara v[2]=3 com v[3]=5 → ok → chama ordenado(3,v).
  • ordenado(3,v): compara v[1]=4 com v[2]=3 4>3 → retorna 0.
  • Resultado final: 0.

Passo 7

Variante tail-recursiva (opcional, útil para entender outra abordagem):
  • Em vez de reduzir n e sempre olhar os últimos dois elementos, podemos usar um índice i que cresce do início do vetor:
    • Função ordenado_idx( i, n, v):
      1. Se i\ge n-1 retornar 1.
      2. Se v[i]>v[i+1] retornar 0.
      3. Retornar ordenado_idx( i+1, n, v).
  • Essa forma é tail-recursiva porque a chamada recursiva é a última operação; se a linguagem fizer otimização, usa O(1) de pilha.

Passo 8

Reconhecimento de detalhes de implementação prática:
  • Cuidado com o tipo de retorno (usar 1 e 0 conforme solicitado).
  • Verificar se o enunciado exige índices começando em 1 em vez de 0. Aqui assumi índice base 0 (convencional em C).
  • Se for necessário tratar n\le 0, a função pode começar testando n\le 1 e retornar 1.

Resposta

int ordenado(int n, int v[]) {
if (n <= 1) return 1;
if (v[n-2] > v[n-1]) return 0;
return ordenado(n-1, v);
}

Exercícios relacionados