Em ciência da computação, recursão é um método de resolver problemas em que a solução se dá por um algoritmo que faz referência a si próprio. Um exemplo clássico é o cálculo do fatorial de um número.
Recursão é o que ocorre quando uma função invoca a si própria. A tais funções dá-se o nome de funções recursivas.
Certas linguagens de programação funcional não possuem estruturas de loop (ciclos, ou laços), e dependem somente de recursão para efetuar uma operação repetidamente. De maneira similar, em linguagens que possuem loops é possível eliminar as funções recursivas utilizando loops.
Portanto há duas maneiras de se executar um trecho de código repetidamente: por iteração (utilizando loops) ou por recursão.
A recursão pode ocorrer não só em código, mas também em estruturas de dados: arrays ou objetos aninhados podem conter referências a um elemento já presente na estrutura.
Exemplos em algumas linguagens
C
void recursiveFunction(int num) {
if (num < 4)
recursiveFunction(num + 1);
printf("%d\n", num);
}
C++
void recursiveFunction(int num) {
if (num < 4)
recursiveFunction(num + 1);
cout<<num;
}
Java
public static int factorial(int N) {
if (N == 1) return 1;
return N * factorial(N-1);
}
Haskell
factorial n = if n == 0 then 1 else n * factorial (n - 1)