Questão de Algoritmos e Estrutura de Dados — Complexidade de Algoritmos — Quadrix 2024
Algoritmos e Estrutura de Dados›Complexidade de Algoritmos
Código
qg349325
Banca
Quadrix
Órgão
CREF - 9ª Região (PR)
Ano
2024
Nível
Superior
Cargo
Técnico de Ensino Superior em Informática
Assinale a alternativa que apresenta a situação em que a recursividade pode ser menos eficiente que a iteração.
AQuando o problema pode ser dividido em subproblemas menores.
BQuando o problema tem múltiplos casos base.
CQuando a profundidade da recursão é muito grande, podendo causar um estouro de pilha.
DQuando a recursão não requer parâmetros.
EQuando o problema é de natureza matemática.
Revelar gabarito e comentário▾
GabaritoC — Quando a profundidade da recursão é muito grande, podendo causar um estouro de pilha.
Comentário gerado por IA. É um apoio ao estudo, ancorado em fontes, mas pode conter imprecisões — confira sempre na fonte oficial (lei, súmula, edital e gabarito da banca). Encontrou um erro? Use “Reportar”.
Recursividade vs Iteração
Gabarito: letra C. A recursão pode ser menos eficiente que a iteração quando a profundidade da recursão é muito grande, pois cada chamada recursiva consome espaço na pilha de execução (stack frame), podendo causar estouro de pilha (stack overflow) e aumento do overhead de chamadas de funções. Enquanto a iteração usa um laço e mantém apenas algumas variáveis, a recursão acumula múltiplos contextos de execução, tornando-se ineficiente em termos de memória e tempo quando a profundidade é excessiva.
Alternativa A — ❌ Incorreta
A divisão em subproblemas menores é justamente uma das vantagens da recursão (paradigma divisão e conquista). Exemplos como merge sort e quicksort usam recursão de forma eficiente.
Alternativa B — ❌ Incorreta
Múltiplos casos base não tornam a recursão menos eficiente; eles são parte da definição e ajudam a encerrar a recursão adequadamente.
Alternativa C — ✅ Correta ⟵ GABARITO
Quando a profundidade da recursão é muito grande, o consumo de pilha pode exceder a capacidade, resultando em estouro de pilha. Além disso, o overhead de chamadas sucessivas torna a recursão mais lenta que a iteração.
Alternativa D — ❌ Incorreta
A ausência de parâmetros não está diretamente relacionada à eficiência; recursão sem parâmetros pode ser usada em casos simples, mas não é um fator de ineficiência.
Alternativa E — ❌ Incorreta
Problemas de natureza matemática são frequentemente resolvidos de forma elegante e eficiente com recursão (ex.: fatorial, Fibonacci), desde que a profundidade não seja excessiva.
NÃO CAIA NESSA!
A banca testa o conhecimento sobre uma limitação prática da recursão: o estouro de pilha. Muitos candidatos podem achar que recursão é sempre pior, mas a ineficiência só ocorre em casos de profundidade excessiva. Lembre-se: em problemas com divisão natural (como árvores), a recursão é eficiente!