Para entender a recursão, você precisa entender a recursão...
Iteração na programação — em um sentido amplo — organização do processamento de dados, na qual as ações são repetidas várias vezes, sem levar a chamadas para si mesmas (ao contrário de %BA%D1%83%D1%80%D1%81%D0%B8%D1%8F" title="Recursão" >Recursões). No sentido estrito — processo de processamento de dados cíclicos em uma etapa.
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:
Você pode perceber que esta descrição nada mais é do que uma função recursiva.
Aqui a primeira linha (
\(n <= 1\)) — este é o caso base (condição final da recursão) e a segunda linha é a transição para a próxima etapa.
| A função fatorial recursiva ficaria assim |
Compare o algoritmo para encontrar o fatorial da maneira usual e não recursiva |
função Fatorial(n: inteiro): inteiro;
começar
se n > 1 então
Fatorial := n * Fatorial(n - 1)
senão
Fatorial := 1;
fim; |
x := 1;
para i := 2 até n faça
x := x * i;
writeln(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.