Pular para o conteúdo principal

Questão de Algoritmos e Estrutura de Dados — Recursividade — FCC 2015

Algoritmos e Estrutura de DadosRecursividade
Código
fc019784
Banca
FCC
Órgão
DPE-SP
Ano
2015
Nível
Médio
Cargo
Programador
O uso da recursividade geralmente permite uma descrição mais clara e concisa dos algoritmos. Em relação aos conceitos e utilização de recursividade, é correto afirmar:
  1. AUm compilador implementa um procedimento recursivo por meio de um deque, no qual são armazenados os dados usados em cada chamada de um procedimento que ainda não terminou de processar.
  2. BUma exigência fundamental é que a chamada recursiva a um procedimento P esteja sujeita a uma condição B, que não deve ser satisfeita em nenhum momento da execução.
  3. CAlgoritmos recursivos são apropriados quando o problema a ser resolvido ou os dados a serem tratados são definidos em termos recursivos, pois isso garante sempre a melhor solução para resolver o problema.
  4. DApenas os dados não globais vão para o deque de controle, pois o estado corrente da computação deve ser registrado para que possa ser recuperado de uma nova ativação de um procedimento recursivo.
  5. ENa prática, é necessário garantir que o nível mais profundo de recursão seja finito e que também possa ser mantido pequeno, pois em cada ativação recursiva de um procedimento P, uma parcela de memória é requerida.
Revelar gabarito e comentário

GabaritoE — Na prática, é necessário garantir que o nível mais profundo de recursão seja finito e que também possa ser mantido pequeno, pois em cada ativação recursiva de um procedimento P, uma parcela de memória é requerida.

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 em Programação

Gabarito: letra E. A recursão utiliza uma pilha de chamadas (stack) para armazenar o estado de cada ativação; cada chamada consome memória, por isso a profundidade deve ser finita e controlada. As demais alternativas contêm erros conceituais, como confundir a estrutura de dados (deque vs. pilha) ou afirmar que a condição de parada nunca deve ser satisfeita.

  1. 1Chamada recursiva
  2. 2Aloca registro na pilha
  3. 3Executa até caso base
  4. 4Desempilha e retorna
LEVEL · soulevel.com.br

Alternativa A — ❌ Incorreta

Afirma que o compilador usa um deque para implementar recursão. Na verdade, utiliza-se uma pilha (stack), onde são empilhados os dados de cada chamada ainda não encerrada.

Alternativa B — ❌ Incorreta

Diz que a condição da chamada recursiva "não deve ser satisfeita em nenhum momento". Isto levaria a recursão infinita. O correto é que deve haver um caso base que eventualmente seja satisfeito para interromper a recursão.

Alternativa C — ❌ Incorreta

Embora problemas recursivos sejam adequados para algoritmos recursivos, isso não garante a melhor solução — muitas vezes a versão iterativa é mais eficiente em tempo e memória.

Alternativa D — ❌ Incorreta

Novamente menciona "deque" (o correto é pilha). Além disso, não são apenas dados não globais que vão para a pilha; também vão variáveis locais, parâmetros e endereço de retorno.

Alternativa E — ✅ Correta ⟵ GABARITO

Correta. Cada chamada recursiva aloca um novo registro de ativação na pilha. Portanto, a profundidade máxima deve ser finita e, na prática, mantida pequena para evitar estouro de memória (stack overflow).

NÃO CAIA NESSA!

As alternativas A e D trocam "pilha" por "deque", um erro comum. A alternativa B inverte o propósito da condição de parada. Fique atento: a recursão sempre requer um caso base que será satisfeito.

Gabarito: letra E.

Link permanente: /questoes/fc019784