Recursão

Olá!
Quando você começa a estudar a Ciência da Computação, você aprende (ou pelo menos deveria aprender) muita matemática. Uma técnica matemática aplicada à essa ciência é recursão.
De acordo com o verbete Recursion, da Wikipedia:

"Recursion in computer science is a method where the solution to a problem depends on solutions to smaller instances of the same problem.[1] The approach can be applied to many types of problems, and is one of the central ideas of computer science."

ou, em Português:

"Recursão na ciência da computação é um método onde a solução de um problema depende de soluções de problemas menores em instâncias do mesmo problema. O método pode ser aplicado em vários tipos de problemas, e é uma das ideias centrais da ciência da computação."

Há também uma frase muito legal para entender a recursão, que diz:

"Para entender a recursão, é preciso primeiro entender a recursão"

Hã? Calma, pequeno padawan. =)
Imagine o seguinte problema: Você está no seu colegial, e o seu professor de matemática que você adora tanto que até deixou você de recuperação pra não sentir saudades, pede uma lista enorme, só com fatoriais. Você, um aluno calmo e consciente, respira fundo e pensa, dentre seus pensamentos matemáticos: "Qual será a relação matemática entre todos esses fatoriais?"
Então, você tem uma luz, daquelas que iluminam quarteirão em dia de apagão, e escreve:

fatorial(n) =
| 1 ,se n = 0
| n * fatorial(n - 1) ,se n > 0

Claro! Se o número que ele pedir for zero, então eu sei que o resultado é 1, por definição. Mas se for maior do que zero, o resultado nada mais é do que ele vezes o fatorial do número anterior à ele! E então você faz no seu rascunho algumas provas reais:

fatorial(1) = 1 * fatorial(0) = 1 * 1 = 1
fatorial(2) = 2 * fatorial(1) = 2 * 1 = 2
fatorial(3) = 3 * fatorial(2) = 3* ( 2*fatorial(1)) = 3* ( 2* ( 1* fatorial(0))) = 3*2*1*1 = 6

Você acaba de entender a recursão!

Passar esse conceito para um algoritmo em C, é fácil. Ficaria dessa forma:
Perceba a estrutura recursiva da função.
Temos o caso base, que encerra a recursão em algum momento, para não entrar em algo infinito:
E então, o passo da recursão, que reduz o problema a uma instância menor, chamando a mesma função
Na grande maioria dos casos (pra não dizer todos), uma solução recursiva pode ser escrita de forma iterativa. Veja o exemplo que eu dei quando falei sobre laços de repetição: A função fatorial, em sua versão iterativa.

Uma função recursiva é, sem dúvida, muito elegante. Hoje, muitas pessoas que estão na área da computação não conseguem utilizar recursão, outras não a entendem, e outras sequer sabem da sua existência. Então, é algo que merece um pouco de estudo e atenção.
E lembre-se: Para fazer um procedimento recursivo, é preciso ter fé! =)

Vou postar mais alguns problemas com resoluções recursivas e, para comparação e estudo, suas soluções iterativas.

Até lá!