Questão 1796236

• Banca: FCC
• Órgão: DPE-SP
• Ano: 2015
• Provas: FCC - 2015 - DPE-SP - Programador
• Disciplina: Algoritmos e Estrutura de Dados
• Assuntos: Algoritmos; Recursividade

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:

• A. Um 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.
• B. Uma 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.
• C. Algoritmos 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.
• D. Apenas 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.
• E. 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.

Gabarito: E

Comentários

• "é necessário garantir que o nível mais profundo de recursão seja finito" - É CLARO que não é necessário. Vários algoritmos recursivos são usados para encontrar boas soluções de problemas NP-completo, em que a condição é uma solução viável, mas que a "profundidade" das soluções é infinita. Tem que ter uma condição de parada, porém não é necessário garantir um nível finito.
  
  Que questão mais errada.

• Rafael Freitas,

  Acho que o que deixa a questão correta é que ela fala "na prática". Toda vez que vc chama um algoritmo recursivo, ele coloca na sua pilha a chamada de onde originou para voltar. Além disso, há uma alocação de memória para isso. Imagina um algoritmo infinito. As máquinas que utilizamos no dia a dia (na prática) iriam apontar problemas na alocação de memória, como muitas vezes já vi em programas em Java.

• É justamente na prática, Rosana. Eu já fiz vários algoritmos recursivos para problemas que tinha uma gama de respostas maior que os computadores conseguem processar. Não é necessário garantir que seja finito. Você tem que encontrar UMA resposta aceitável, e não passar por todas elas armazenando-as na memória. Se a resposta não servir, descarte-a. Faça um bom código e gerenciamento de memória que você não terá este problema.
  

• Rafael Freitas, no caso dos problemas NP-completo existem infinitas condições que atendem o problema, porém uma boa solução é considerada como a mais certa e o algoritmo atinge o seu critério de parada, isto é o nivel mais profundo da recursão, quando o algoritmo encontrou uma resposta satisfatoria. Esta resposta é configurada por você no critério de parada, o que tornam finitas as possibilidades!

• a) E. Pessoal quando temos um contexto de variáveis é criado uma estrutura de pilha (para o sistema operacional) registrando todos os valores na memória. Quando falamos em uma nova chamada da própria função (recursividade), um novo elemento é posta a pilha (operação 'push' com todas as varíaveis e seus respectivos valores passados). O item 'deque' macula o item. 

  b) E. A condição B (que deve ser trivial) é fundamental para a parada de execução do algoritmo. Se não tivermos ela, o algoritmo ficará em 'loop'.

  c) E. Nem sempre eles são a melhor solução, já que em geral os algortimos interativos são. 

  d) E. Variáveis globais e locais para cada chamada da função recursiva vão para o estado. 

  e) C

   

• Força Guerreiro!!!!!!