TL;DR
Todo código recursivo pode ser traduzida numa forma iterativa, porém alguns algoritmos são naturalmente recursivos e mais facilmente representados desta forma.
Pense, por exemplo, em percorrer todos os nós de uma árvore ou grafo, processar todos os arquivos de um diretório e subdiretórios e assim por diante.
No modo iterativo você é responsável por gerenciar manualmente o estado de cada etapa do algoritmo usando alguma estrutura de dados, muitas vezes uma pilha, enquanto no modo recursivo você delega esta função à sua linguagem de programação, ao fazer uso de variáveis e parâmetros que são automaticamente alocadas na pilha de execução no início de cada execução do método método.
Exemplo
Para responder às perguntas, considere algo um pouquinho mais complexo. Extraí o pseudo-código para percorrer árvores da Wikipédia.
Método recursivo
postorder(node)
if node == null then return
postorder(node.left)
postorder(node.right)
visit(node)
Método iterativo
iterativePostorder(node)
parentStack = empty stack
lastnodevisited = null
while (not parentStack.isEmpty() or node ≠ null)
if (node ≠ null)
parentStack.push(node)
node = node.left
else
peeknode = parentStack.peek()
if (peeknode.right ≠ null and lastnodevisited ≠ peeknode.right)
node = peeknode.right
else
visit(peeknode)
lastnodevisited = parentStack.pop()
Respostas
1ª Qual a vantagem de usarmos uma Função Recursiva?
No seu exemplo há pouca vantagem, mas no que coloquei acima, vemos claramente que o método recursivo:
- Expressa melhor a funcionalidade. Programação funcionar faz tudo pesado desse dessa capacidade.
- É mais compacto. Menos código significa manutenção mais fácil, menor possibilidade de erros e assim por diante.
- Gerenciamento automático do estado. No exemplo iterativo foi usada uma pilha (stack). Pense agora em linguagens onde o gerenciamento de memória não é automático. Em C, por exemplo, você teria que adicionar código para alocar e liberar elementos da pilha em cada iteração.
2ª Como fica o consumo de memória?
Depende da função. Geralmente você deveria fazer uma análise de complexidade de memória e tempo para analisar as diferenças, mas é um tanto óbvio que, na grande maioria dos casos, as rotinas recursivas consomem mais memória e necessitam de mais ciclos de execução.
Rotinas recursivas geralmente usam mais memória por realocar as variáveis a cada chamada recursiva, mas rotinas iterativas podem usar a mesma quantidade de memória se os valores forem salvos em listas ou pilhas, por exemplo.
No modo iterativo você tem o controle, para o bem ou para o mal. Existe a possibilidade de criar uma rotina mais otimizada que a versão recursiva. Mas não se deve tomar isso como uma regra, afinal existem excelentes implementações recursivas que são mais eficientes do que a média das implementações iterativas.
Além disso, a eficiência depende grandemente do número de execuções e do nível de recursão. Assim como rotinas de ordenação, algumas implementações funcionam melhor quando há poucas iterações e outras quando há mais iterações. Algumas implementações recursivas são melhores para processamentos pequenos. Veja, por exemplo, neste site que o desempenho para o Fibonacci onde n <= 5
foi melhor para a versão recursiva.
Num exemplo bem simples, a função recursiva de Fibonacci tem complexidade exponencial enquanto a versão pode ser implementada com duas ou três variáveis simples e, portanto, tem uso de memória constante.
Por outro lado, quase sempre as rotinas recursivas acabam precisando ser reescritas em sua versão iterativa quando o número de elementos ou números processados é grande, afinal a recursividade tem um limite sensível tanto de memória quanto de empilhamento de dados.
E além de tudo isso, existem técnicas que podem melhoram o desempenho e a capacidade das rotinas recursivas, sendo exemplos disso:
3ª Eu devo utilizar uma função recursiva ao invés de um Loop de Repetição comum (e.g. for/while)? Quais seriam as situações ideais para o uso de funções recursivas?
Deve apenas se o algoritmo for melhor expresso recursivamente e se o uso geral daquele algoritmo não vai exceder os limites de recursividade.
Acredito que as situações ideais tenham sido exemplificadas acima, isto é:
- Algoritmos inerentemente recursivos, melhor expressos neste formato
- Uso computacional é moderado, de modo a não exceder os limites de recursão