Uma chamada de função em C (e normalmente em qualquer linguagem) usa um recurso do S.O. (sistema operacional) chamado de pilha (em inglês, stack). A pilha é usada para armazenar os endereços de retorno das funções bem como os seus parâmetros. A pilha de endereços funciona como uma pilha de papeis. Cada vez que uma nova função é executada, o endereço de retorno (aquele no qual o programa deve retomar a execução após a chamada) é guardado na pilha. A função é então executada. Ao seu término, o endereço de retorno é retirado da pilha e a execução continua a partir deste endereço. Veja o exemplo abaixo de como funciona a pilha de endereços (e parâmetros).

Exemplo 1: A função A chama a função B que chama a função C:
 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26

#include <stdio.h> int funcao_C(int c) {   return(c/2); } int funcao_B(int i) {   int k;   k=funcao_C(i-3);   return(k); } int funcao_A(int n) {   int x;   x=funcao_B(n-1);   return(x); } void main() {   printf("resultado: %d\n",     funcao_A(10)); }

pilha executando  a linha 18:  int x parametro 10 linha 26 início da pilha

pilha executando  a linha 11:  int k parametro 9 linha 19 int x parametro 10 linha 26 início da pilha

pilha executando  a linha 5:  parametro 6 linha 12 int k parametro 9 linha 19 int x parametro 10 linha 26 início da pilha

 
 
Cada vez que uma função é chamada, ela coloca na pilha nesta ordem:

• O endereço de retorno que é onde o programa deve continuar executando após retornar da função chamada. No exemplo o endereço de retorno é representado por "linha x", onde x é o número da linha de retorno;
• Todos os parâmetros usados na chamada da função. Os parâmetros que são passados por valor são copiados para a pilha criando uma cópia do valor original. É por isso que quando modificamos uma variável de um tipo elementar (int, char, float ou double) que é um parâmetro, o seu valor original fora da função não é alterado;
• Todas as variáveis locais criadas pela função. As variáveis locais são criadas na pilha e quando a função termina, elas somem porque são apagadas da pilha.

O funcionamento da pilha é muito importante para entender como funcionam as chamadas recursivas. Se você tiver alguma dúvida, não hesite em consultar o professor!
 

O exemplo típico: o cálculo fatorial

Para implementarmos o cálculo fatorial recursivo é necessário entender o problema do ponto de vista recursivo. Uma chamada recursiva é usada em problemas que podem ser reduzidos a um outro problema menor a cada chamada da função. Neste exemplo, o fatorial pode ser simplificado se a cada chamada eliminarmos um número da sequência. Isso é facilmente representado matematicamente:

n!(K) = n!(K-1) . K
n!(0) = 1

Veja abaixo a implementação do fatorial recursivo:
 

#include <stdio.h> int fatorial(int K) {   if (K==0) return(1);   return(fatorial(K-1)*K); } void main() {   int K=7;   printf("O fatorial de %d e' %d\n", K, fatorial(K)); }

A função recursiva nada mais faz do que testar a sua condição de parada e chamar a função recursiva reduzindo o seu índice (parâmetro K). A redução do problema na chamada também é impressindível para que a função não trave (entre em loop infinito).

Um exemplo gráfico

Imagine o seguinte problema:

Um pai fala para o filho:
- Filho, está vendo aquela parede ali? Ande para frente de modo que a cada movimento, você chegue na metade do caminho entre você e a parede. Quando você encostar na parede, eu te dou tudo o que quiser!

Quando o filho chegará a parede? Nunca! Porque teoricamente se ele sempre dividir o espaço que falta em dois, ele nunca o percorrirá por completo, mesmo que a distância seja mínima. Se o seu pai já te falou isso então agora você sabe porque ele não se preocupou! :-)

Imagine uma função recursiva que faça desenhos utilizando sempre como coordenadas as últimas coordenadas desenhadas divididas ao meio. Esta função irá desenhar na tela algo que a princípio fica difícil de imaginar, e que o resultado é sempre interessante para analisarmos como funcionam as funções recursivas.

Abaixo está um programa que usa uma função recursiva que recebe quatro coordenadas. Em seguida faz um círculo no meio e chama ela mesma recursivamente para desenhar mais círculos acima, abaixo, a direita e a esquerda, reduzindo o espaço de desenho e também o diâmetro do círculo. Neste exemplo, o programa lê o número máximo de iterações do usuário.
 

#include <stdio.h> #include <stdlib.h> #include <graphics.h> #include <conio.h> int N; // desenha um circulo no meio e chama a funcao mais 4 vezes // recursivamente reduzindo o espaco de desenho e o tamanho // do circulo. A variavel N e' o controle de parada void desenha(int x1,int y1,int x2,int y2,int diam,int N) {   int mx;   // posicao X do circulo   int my;   // posicao Y do circulo   if (N>0) {    // condicao de parada!     // calcula a posicao do circulo no meio da tela     mx=(x1+x2)/2;     my=(y1+y2)/2;     // primeiro desenha os circulos menores     desenha(x1,y1,mx,my,diam/2,N-1);     desenha(mx,y1,x2,my,diam/2,N-1);     desenha(x1,my,mx,y2,diam/2,N-1);     desenha(mx,my,x2,y2,diam/2,N-1);     // agora desenha o circulo maior     setcolor(N);     circle(mx,my,diam);   } } void main() {   int gdriver=DETECT; // numero da placa de video usada   int gmode;          // numero do modo de video usado   int errorcode;      // codigo de erro retornado por "initgraph"   // le^ o numero de iteracoes e verifica se e' "aceitavel"   printf("Entre com o numero de iteracoes (1-10): ");   scanf("%d%*c",&N);   if (N>=1 && N<=10) {     // Tenta inicializar o modo grafico detectando a placa de video     initgraph(&gdriver, &gmode, "");     errorcode = graphresult();     if (errorcode != grOk)     {       printf("Erro no modo graifco: %s\n", grapherrormsg(errorcode));       exit(1);     }     // chama a funcao de desenho usando a tela toda inicialmente     desenha(0,0,getmaxx(),getmaxy(),32,N);     getch();     closegraph(); // Volta para a tela de texto   } }