Iteração e Recursão
Gabarito: letra E. Iteração e recursão são formalmente equivalentes: toda iteração pode ser expressa como recursão e vice-versa, ainda que a transformação possa aumentar a complexidade do código. Esse é um princípio fundamental da ciência da computação, corroborado pela teoria da computabilidade (Máquina de Turing e cálculo lambda são Turing-completos).
A banca testa o conhecimento sobre essa equivalência. Muitos candidatos acreditam erroneamente que iteração e recursão são mutuamente exclusivas ou que uma é sempre superior à outra, mas a verdade é que ambas são equivalentes em poder expressivo.
Alternativa | Afirmação | Análise | Veredito |
|---|
A | Nem toda iteração pode ser transformada em recursão | Falsa: toda iteração é conversível em recursão (ex.: usando função que se autochama para simular o laço) | ❌ Incorreta |
B | Nem toda recursão pode ser transformada em iteração | Falsa: toda recursão é conversível em iteração (ex.: com pilha explícita) | ❌ Incorreta |
C | Uma iteração é sempre melhor que uma recursão | Falsa: não há superioridade absoluta; iteração é mais eficiente em memória, mas recursão pode ser mais clara para problemas recursivos | ❌ Incorreta |
D | Uma recursão é sempre melhor que uma iteração | Falsa: recursão pode causar estouro de pilha; iteração é mais adequada para loops simples | ❌ Incorreta |
E | Iteração e recursão são equivalentes, e qualquer iteração pode ser transformada em recursão e qualquer recursão pode ser transformada em iteração | Verdadeira: ambas são Turing-completas e formalmente equivalentes | ✅ Correta |
Alternativa A — ❌ Incorreta
Afirma que "nem toda iteração pode ser transformada em recursão". Isso é falso: qualquer algoritmo iterativo pode ser reescrito de forma recursiva (por exemplo, usando uma função que chama a si mesma para simular o laço). A transformação pode exigir o uso de parâmetros adicionais, mas é sempre possível.
Alternativa B — ❌ Incorreta
Afirma que "nem toda recursão pode ser transformada em iteração". Também é falsa: toda função recursiva pode ser convertida em uma versão iterativa, geralmente com o auxílio de uma pilha explícita para gerenciar as chamadas pendentes (como ocorre na tradução de recursão para código de máquina).
Alternativa C — ❌ Incorreta
Diz que "uma iteração é sempre melhor que uma recursão". Não há relação de superioridade absoluta: iteração tende a ser mais eficiente em termos de memória (evita overhead de pilha), mas recursão pode tornar o código mais claro e elegante para problemas naturalmente recursivos (ex.: árvores, Hanoi). A escolha depende do contexto.
Alternativa D — ❌ Incorreta
Afirma o oposto: "uma recursão é sempre melhor que uma iteração". Mesmo erro da anterior: não há "sempre melhor". Recursão pode causar estouro de pilha em profundidades grandes; iteração pode ser mais adequada para loops simples.
Alternativa E — ✅ Correta ⟵ GABARITO
Esta é a correta. Conforme abordado, iteração e recursão são equivalentes do ponto de vista da computabilidade: qualquer algoritmo iterativo pode ser convertido em recursivo e qualquer algoritmo recursivo pode ser convertido em iterativo. O conteúdo de apoio reforça: "Cada algoritmo recursivo possui um algoritmo iterativo equivalente e vice-versa, mas que pode ter mais ou menos complexidade em sua construção". Portanto, a afirmativa está plenamente de acordo com o conhecimento consolidado.
Gabarito: letra E.