Projete em pseudocódigo uma função recursiva que verifica se uma lista de inteiros L está estritamente…

Questão

Projete em pseudocódigo uma função recursiva que verifica se uma lista de inteiros L está estritamente crescente (cada elemento maior que o anterior). Explique a correção da recursão e analise sua complexidade temporal.

✍️ Questão dissertativa: veja abaixo a resposta esperada e a explicação.

Resposta esperada

Pseudocódigo: func crescente(L): se len(L) <= 1 então retorne verdadeiro se L[0] >= L[1] então retorne falso retorne crescente(L[1:]) Corretude (esboço): - Caso base: listas de tamanho 0 ou 1 são estritamente crescentes por definição, então função retorna verdadeiro. - Passo indutivo: suponha que crescente(L[1:]) verifica corretamente a propriedade para listas menores. Se L[0] < L[1] e a sublista L[1:] é estritamente crescente, então toda L é estritamente crescente. Se L[0] >= L[1] função detecta e retorna falso imediatamente. - Assim, por indução, a função é correta. Complexidade temporal: - Cada chamada recursiva faz uma comparação e reduz o tamanho da lista em 1, resultando em O(n) comparações para lista de tamanho n. O custo espacial depende da profundidade de recursão O(n) na chamada de pilha (ou O(1) se transformada em iteração).

Explicação

A função verifica a propriedade de estrita crescente ao comparar elementos adjacentes e, se necessário, chama a si mesma com a sublista restante. O caso base garante que listas pequenas são tratadas corretamente, enquanto o passo indutivo assegura que a propriedade se mantém ao longo da lista. A análise da complexidade temporal demonstra que a função é linear em relação ao tamanho da lista, o que é eficiente para essa tarefa.

Raio-X da questão

Questões parecidas com resolução

• Projete em pseudocódigo uma função recursiva maximo(L) que recebe uma lista não vazia de inteiros e retorna o maior…
• Projete em pseudocódigo uma função recursiva subsequencias(L) que recebe uma lista L de inteiros e retorna a lista de…
• Projete em pseudocódigo um algoritmo recursivo max_recursive(L) que recebe uma lista não vazia L de inteiros e retorna o…
• Projete em pseudocódigo uma função recursiva quicksort(L) que ordena uma lista L de inteiros em ordem não crescente…
• Projete um algoritmo em pseudocódigo que receba uma lista L de n inteiros e retorne uma nova lista em que todos os…
• Projete em pseudocódigo uma função recursiva permutar(L) que recebe uma lista L com n elementos distintos e retorna uma…

Todas as questões de Programação - Linguagem de programação