A aula anterior foi nossa primeira aula sobre recursão. Na aula de hoje veremos em detalhes como funciona um processo recursivo e para isso usaremos o código desenvolvido na aula 153.

#include <stdio.h>
#include <stdlib.h>

void imprimir(int n){
    if(n == 0)
        printf("%d ", n);
    else{
        //printf("%d ", n);
        imprimir(n - 1);
        //printf("%d ", n);
    }
}

int main () {

    int n;

    printf("Digite um valor maior que zero: ");
    scanf("%d", &n);

    imprimir(n);

    return 0;
}

Imprimindo uma sequência decrescente de números

Vamos ver primeiro a versão que imprime o valor de n e só depois faz a chamada recursiva.

void imprimir(int n){
    if(n == 0)
        printf("%d ", n);
    else{
        printf("%d ", n);
        imprimir(n - 1);
    }
}

Toda chamada recursiva é gerenciada pelo Sistema Operacional, então você, programador, não precisa se preocupar com vários detalhes que são responsabilidade do SO. Dentre esses detalhes estão os processos de empilhar e desempilhar os valores das variáveis antes e após cada chamada recursiva.

Como o computador não sabe de antemão se há alguma coisa a ser feita após uma chamada recursiva, então é necessário salvar o escopo daquele momento (situação de todas aas variáveis locais).

Imagine que nosso procedimento imprimir foi chamado lá na função main com o valor 5.

O if será falso, indo para o else.
Será impresso o valor de n (5) e, sem seguida, será feita a primeira chamada recursiva com o valor 4 (n – 1).
pilha -> 5
saída -> 5

Esta é a primeira chamada recursiva.
O if será falso, indo para o else.
Será impresso o valor de n (4) e, sem seguida, será feita a segunda chamada recursiva com o valor 3 (n – 1).
pilha -> 5 4
saída -> 5 4

Esta é a segunda chamada recursiva.
O if será falso, indo para o else.
Será impresso o valor de n (3) e, sem seguida, será feita a terceira chamada recursiva com o valor 2 (n – 1).
pilha -> 5 4 3
saída -> 5 4 3

Esta é a terceira chamada recursiva.
O if será falso, indo para o else.
Será impresso o valor de n (2) e, sem seguida, será feita a quarta chamada recursiva com o valor 1 (n – 1).
pilha -> 5 4 3 2
saída -> 5 4 3 2

Esta é a quarta chamada recursiva.
O if será falso, indo para o else.
Será impresso o valor de n (1) e, sem seguida, será feita a quinta chamada recursiva com o valor 0 (n – 1).
pilha -> 5 4 3 2 1
saída -> 5 4 3 2 1

Esta é a quinta chamada recursiva.
O if será verdadeiro.
Será impresso o valor de n (0) e, sem seguida, como não há nada a ser feito, o procedimento é finalizado, voltando exatamente para o momento onde foi feita a última chamada recursiva, quando n valia 1.
n -> 1
pilha -> 5 4 3 2
saída -> 5 4 3 2 1 0

Os valores das variáveis são desempilhados e, como não há nada mais a ser feito, o procedimento imprimir é finalizado, voltando exatamente para o momento onde foi feita a última chamada recursiva, quando n valia 2.
n -> 2
pilha -> 5 4 3
saída -> 5 4 3 2 1 0

Os valores das variáveis são desempilhados e, como não há nada mais a ser feito, o procedimento imprimir é finalizado, voltando exatamente para o momento onde foi feita a última chamada recursiva, quando n valia 3.
n – > 3
pilha -> 5 4
saída -> 5 4 3 2 1 0

Os valores das variáveis são desempilhados e, como não há nada mais a ser feito, o procedimento imprimir é finalizado, voltando exatamente para o momento onde foi feita a última chamada recursiva, quando n valia 4.
n – > 4
pilha -> 5
saída -> 5 4 3 2 1 0

Os valores das variáveis são desempilhados e, como não há nada mais a ser feito, o procedimento imprimir é finalizado, voltando exatamente para o momento onde foi feita a última chamada recursiva, quando n valia 5.
n – > 5
pilha ->
saída -> 5 4 3 2 1 0

Os valores das variáveis são desempilhados e, como não há nada mais a ser feito, o procedimento imprimir é finalizado. Neste momento perceba que a pilha de recursão está vazia. Isso significa que acabaram as chamadas recursivas. A execução do nosso programa volta para a função main, para executar o que estiver após a chamada ao procedimento imprimir.

Este processo aqui apresentado ocorre toda vez que utilizamos recursão, independente do problema que esteja sendo resolvido.