Escreva uma função recursiva que recebe um número inteiro positivo
, um vetor
contendo
números inteiros e verifica se este vetor está ordenado crescentemente. Esta função deve devolver os valores 1 e 0 , indicando, respectivamente, se
está ou não ordenado.
Passo 1
O enunciado pede: escrever uma função recursiva que recebe um inteiro positivo
e um vetor
com
inteiros e verifica se o vetor está ordenado crescentemente. A função deve devolver
se
está ordenado e
caso contrário.
Informações relevantes dadas:
- Entrada: um inteiro positivo
(ou seja, ) e um vetor com inteiros. - Saída esperada: valor inteiro
(verdadeiro) se o vetor estiver ordenado crescentemente, ou (falso) caso não esteja. - Interpretação adotada aqui para “ordenado crescentemente”: cada elemento é menor ou igual ao próximo, isto é, para todo índice
válido vale . (Se o professor exigir estritamente crescente, troque por .)
O que a função precisa fazer, em termos claros:
- Verificar se para todos
com tem-se . - 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
(ou ) está trivialmente ordenado. Então se devolvemos . - Passo recursivo: para
podemos comparar os dois últimos elementos e . - Se
, então há uma violação da ordenação e devolvemos . - Caso contrário, os dois últimos estão em ordem relativa; a ordenação do vetor inteiro depende de os primeiros
elementos estarem ordenados. Então chamamos recursivamente a função em .
- Se
- Recorrendo dessa forma, cada chamada reduz
em até atingir a base .
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(
, ): - Se
então retornar . (Base: vetor unitário é ordenado.) - Se
então retornar . (Encontrou inversão.) - Caso contrário, retornar ordenado(
, ). (Verifica o prefixo de tamanho .)
- Se
Explicação detalhada de cada passo:
- Linha 1 (base): quando
não existem pares para comparar, logo o vetor está ordenado. - Linha 2: comparar os elementos nas posições
e é 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
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
até
.
Passo 4
Prova intuitiva de correção por indução (para aumentar confiança, útil na prova):
- Caso base: para
a função retorna ; isso é correto porque um único elemento está ordenado. - Passo indutivo: suponha que para todo
a função retorna se e somente se os primeiros elementos estão ordenados. Para : - Se
, a função retorna e isso é correto (há uma inversão). - Se
, a função retorna o resultado de ordenado( , ). Pelo passo indutivo, essa chamada devolve sse os primeiros elementos estão ordenados. Como também temos , conclui-se que todos os pares consecutivos entre e estão em ordem, logo todo o vetor de tamanho está em ordem. Assim a função retorna exatamente quando o vetor de tamanho está ordenado. Isso fecha a indução.
- Se
Passo 5
Complexidade e limitações práticas:
- Tempo: cada chamada faz uma comparação e, no pior caso, faz
chamadas recursivas; portanto o tempo é . - Espaço (recursão): a profundidade de recursão é
, portanto utiliza-se 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 , 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):
,
.
- Chamada ordenado(4,v): compara
com → → chama ordenado(3,v). - Chamada ordenado(3,v): compara
com → → chama ordenado(2,v). - Chamada ordenado(2,v): compara
com → → chama ordenado(1,v). - Chamada ordenado(1,v):
retorna . Todas as chamadas retornam .
Exemplo 2 (não ordenado):
,
.
- ordenado(4,v): compara
com → ok → chama ordenado(3,v). - ordenado(3,v): compara
com → → retorna . - Resultado final:
.
Passo 7
Variante tail-recursiva (opcional, útil para entender outra abordagem):
- Em vez de reduzir
e sempre olhar os últimos dois elementos, podemos usar um índice que cresce do início do vetor: - Função ordenado_idx(
, , ): - Se
retornar . - Se
retornar . - Retornar ordenado_idx(
, , ).
- Se
- Função ordenado_idx(
- Essa forma é tail-recursiva porque a chamada recursiva é a última operação; se a linguagem fizer otimização, usa
de pilha.
Passo 8
Reconhecimento de detalhes de implementação prática:
- Cuidado com o tipo de retorno (usar
e conforme solicitado). - Verificar se o enunciado exige índices começando em
em vez de . Aqui assumi índice base (convencional em C). - Se for necessário tratar
, a função pode começar testando e retornar .
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);
}
if (n <= 1) return 1;
if (v[n-2] > v[n-1]) return 0;
return ordenado(n-1, v);
}