Isso depende do seu ponto de vista.
Se você olhar para a teoria da computabilidade , a iteração e a recursão são igualmente expressivas . O que isto significa é que você pode escrever uma função que calcula algo, e não importa se você o faz recursivamente ou iterativamente, você será capaz de escolher ambas as abordagens. Não há nada que você possa calcular recursivamente, o qual você não pode calcular iterativamente e vice-versa (embora o funcionamento interno do programa possa ser diferente).
Muitas linguagens de programação não tratam a recursão e a iteração da mesma forma e por boas razões. Geralmente, , a recursão significa que o compilador / linguagem lida com a pilha de chamadas, e iteração significa que você pode ter que lidar com as pilhas sozinho.
No entanto, existem linguagens - especialmente linguagens funcionais - em que coisas como loops (for, while) são de fato apenas açúcar sintático para recursão e implementadas por trás do cenas dessa maneira. Isso geralmente é desejável em linguagens funcionais, porque elas geralmente não têm o conceito de loop, e adicioná-lo tornaria seu cálculo mais complexo, por uma pequena razão prática.
Então não, eles não são intrinsecamente iguais . Eles são igualmente expressivos , significando que você não pode computar algo iterativamente que você não pode calcular recursivamente e vice-versa, mas é sobre isso, no caso geral (de acordo com a tese de Church-Turing).
Note que estamos falando de programas recursivos aqui. Existem outras formas de recursão, e. em estruturas de dados (por exemplo, árvores).
Se você olhar de um ponto de vista da implementação , a recursão e a iteração não serão as mesmas. A recursão cria um novo quadro de pilha para cada chamada. Cada passo da recursão é independente, obtendo os argumentos para a computação do próprio receptor.
Os loops, por outro lado, não criam quadros de chamada. Para eles, o contexto não é preservado em cada etapa. Para o loop, o programa simplesmente retorna ao início do loop até que a condição do loop falhe.
Isso é muito importante saber, já que pode fazer diferenças bastante radicais no mundo real. Para recursão, todo o contexto deve ser salvo em todas as chamadas. Para a iteração, você tem um controle preciso sobre quais variáveis estão na memória e o que é salvo no local.
Se você olhar dessa maneira, verá rapidamente que, para a maioria dos idiomas, a iteração e a recursão são fundamentalmente diferentes e possuem propriedades diferentes. Dependendo da situação, algumas das propriedades são mais desejáveis do que outras.
A recursão pode tornar os programas mais simples e fáceis de testar e prova . Converter uma recursão em iteração geralmente torna o código mais complexo, aumentando a probabilidade de falha. Por outro lado, a conversão para a iteração e a redução da quantidade de quadros de pilha de chamadas podem economizar muita memória necessária.