Recursividade

Recursividade, o que é?
Eis um assunto que tem de ser visto com todo o cuidado, para não restarem dúvidas.
Uma função recursiva será uma função em cuja definição se recorre à própria função. Um exemplo muito usado é o do cálculo de n! (factorial de n): se soubermos (n-1)!, então calcular n! é facílimo, basta multiplicar n por (n-1)!:

int factorial (int n)
{
   return n * factorial (n-1);
}

E isso basta? Não! Não basta. Assim, nunca mais pára! Se quiséssemos calcular 5!, por exemplo, iríamos obter sucessivamente


5 * 4!
5 * 4 * 3!
5 * 4 * 3 * 2!
5 * 4 * 3 * 2 * 1!
5 * 4 * 3 * 2 * 1 * 0!
5 * 4 * 3 * 2 * 1 * 0 * (-1)!
...

Precisamos claramente de uma instrução que indique que não é necessário continuar o processo, uma vez que chegamos a um valor conhecido da função, e podemos retroceder. Por exemplo

int factorial (int n)
{
   if (n == 0) return 1;
      else return n * factorial (n-1);
}

que permite que agora tudo corra bem:

5 * 4!
5 * 4 * 3!
5 * 4 * 3 * 2!
5 * 4 * 3 * 2 * 1!
5 * 4 * 3 * 2 * 1 * 1
5 * 4 * 3 * 2 * 1
5 * 4 * 3 * 2
5 * 4 * 6
5 * 24
120

e obtenhamos o resultado correcto.
Temos de voltar a isto, mas acompanhados de Fibonacci.