Recursão e iteração
Para entender a recursão, você precisa entender a recursão...
Iteração na programação -
uma etapade um processo cíclico de processamento de dados.
Freqüentemente, algoritmos iterativos na etapa atual (iteração) usam o resultado da mesma operação ou ação calculada nas etapas anteriores. Um exemplo desses cálculos é o cálculo das relações de recorrência.
Um exemplo simples de valor recursivo é o fatorial:
\(N!=1 \cdot 2 \cdot 3 \cdot \ ... \ \cdot N\).
O cálculo do valor em cada etapa (iteração) é
\(N=N \cdot i\) . Ao calcular o valor de
\(N\), tomamos o valor já armazenado
\(N\).< br />
O fatorial de um número também pode ser descrito usando a
fórmula recorrente:
\(\begin{equation*} n!= \begin{cases} 1 &\text{n <= 1,}\\ (n-1)! \cdot n &\text{n > 1.} \end{casos} \end{equação*}\)
Você pode perceber que esta descrição nada mais é do que uma função recursiva.
Aqui, a primeira linha (
\(n <= 1\)) é o caso base (condição de término da recursão) e a segunda linha é a transição para a próxima etapa. < br />
| Função fatorial recursiva |
Algoritmo iterativo |
static int Fatorial(int n){
se (n > 1)
return n * Fatorial(n - 1);
caso contrário, retorne 1;
}
|
int x = 1;
for (int i = 2; i <= n; i++)
x = x * i;
Console.WriteLine("%d", x);
|
Deve ser entendido que as chamadas de função envolvem alguma sobrecarga adicional, portanto, um cálculo fatorial não recursivo será um pouco mais rápido.
Conclusão: onde você pode escrever um programa com um algoritmo iterativo simples, sem recursão, então você precisa escrever sem recursão. Ainda assim, existe uma grande classe de problemas onde o processo computacional é implementado apenas por recursão.
Por outro lado, algoritmos recursivos costumam ser mais compreensíveis.