Funções e procedimentos recursivos com a linguagem C

Nesta aula vamos iniciar o estudo de funções e procedimentos recursivos com a linguagem C. Uma função ou um procedimento recursivo chama a si mesmo durante a execução. É um processo de repetição. Por ser uma repetição, toda função e procedimento recursivo precisa obrigatoriamente de um ponto de parada para finalizar a recursão, evitando assim um loop infinito.

Para facilitar o entendimento de como funciona a recursão vamos a um exemplo: imprimir todos os números inteiros no intervalo de 0 até N onde N é um número inteiro maior que zero informado pelo usuário.

Este problema é facilmente resolvido com uma repetição do tipo for. Contudo, não usaremos esta repetição para resolver este problema e irei utiliza-lo para introduzir a ideia de recursão por sua simplicidade.

Todo processo recursivo é uma repetição, porém uma repetição um pouco diferente das que aprendemos até o momento. Como já vimos, toda repetição precisa de uma condição de parada, senão teremos um loop infinito. Isso também é válido para todo processo recursivo.

Como o objetivo em nosso exemplo é apenas imprimir uma sequência de números, faremos um procedimento e não uma função (pois não há necessidade de nenhum retorno). Este procedimento receberá o valor N digitado pelo usuário, assim.

// protótipo do procedimento imprimir
void imprimir(int n){
    // aqui ficará nosso código
}

Como mencionei, todo processo recursivo precisa de um ponto de parada. Iniciamos nosso procedimento testando se N é igual a zero.

Por que igual a zero?

Zero é um valor fixo que delimita uma das extremidades do intervalo que queremos imprimir. A outra extremidade é delimitada por N, que é um valor variável informado pelo usuário. Assim, não é possível verificar se N é igual a 50 ou igual a 100, pois não sabemos se o usuário irá digitar 50, 100 ou ainda outro valor diferente. Contudo, o limite inferior sempre será zero para este exemplo.

Dessa forma chegamos a algo assim:

// protótipo do procedimento imprimir
void imprimir(int n){
    // aqui ficará nosso código
    if(n == 0)
        printf("%d ", n);
}

Neste momento, se o procedimento imprimir for chamado na função main passando como parâmetro o valor zero, o teste será verdadeiro, será impresso o valor zero e será finalizada.

E se n for diferente de zero?

Agora faremos o trecho que ficará dentro da cláusula else, quando o valor de n for maior que zero.

Como nós queremos imprimir todos os valores entre zero e n e n ainda não é zero, então iremos imprimir n e, em seguida, chamar novamente o procedimento imprimir. Contudo, passando como parâmetro agora n – 1. Eis nossa chamada recursiva.

Perceba que estamos chamando dentro do procedimento imprimir o próprio procedimento imprimir.

// protótipo do procedimento imprimir
void imprimir(int n){
    // aqui ficará nosso código
    if(n == 0)
        printf("%d ", n);
    else{
        printf("%d ", n); // imprime o valor de n
        imprimir(n - 1); // chama o procedimento imprimir para n - 1
    }
}

Como a chamada recursiva foi feita com o valor da subtração n – 1, em algum momento o valor resultante será igual a zero, o teste no if será verdadeiro, será impresso o valor zero e o procedimento imprimir será finalizado.

Mas isso vai imprimir uma sequência decrescente, de n até 0! Como imprimir uma sequência crescente de 0 até n?

Verdade. Isso irá imprimir uma sequência decrescente. Perceba que primeiro estamos imprimindo o valor de n para só depois fazer a chamada recursiva para n – 1. Isso irá gerar uma saída no terminal assim:

Saída: n n-1 n-2 … 3 2 1 0

Para obtermos uma sequência crescente, de 0 até n, basta invertermos a ordem das coisas, ou seja, basta fazermos primeiro a chamada recursiva para n – 1 e apenas depois imprimir o valor de n, assim:

// protótipo do procedimento imprimir
void imprimir(int n){
    // aqui ficará nosso código
    if(n == 0)
        printf("%d ", n);
    else{
        imprimir(n - 1); // chama o procedimento imprimir para n - 1
        printf("%d ", n); // imprime o valor de n
    }
}

Agora, perceba que, enquanto n for diferente de zero, primeiro é feito uma chamada recursiva para n – 1 e só depois é feito a impressão de n.

Imagine que foi digitado o valor 3 para n.
3 é igual a zero?
falso. Vai para o else.
A primeira instrução dentro do else é uma chamada recursiva. O computador salva o valor de n em uma estrutura chamada pilha de recursão (pilha -> 3) e faz a chamada recursiva para n – 1.

2 é igual a zero?
falso. Vai para o else.
A primeira instrução dentro do else é uma chamada recursiva. O computador salva o valor de n na pilha de recursão (pilha -> 3, 2) e faz a chamada recursiva para n – 1.

1 é igual a zero?
falso. Vai para o else.
A primeira instrução dentro do else é uma chamada recursiva. O computador salva o valor de n na pilha de recursão (pilha -> 3, 2, 1) e faz a chamada recursiva para n – 1.

0 é igual a zero?
verdadeiro.
Imprime o valor de n e finaliza o procedimento imprimir.

Para onde volta a execução do nosso programa?

Lembra que foram feitas chamadas recursivas? Quando o procedimento imprimir é finalizado, o computador começa agora o processo de desempilhar todos os valores empilhados durante as chamadas recursivas.

Ao voltar para a última chamada recursiva feita (imprimir(0) que foi finalizada) será então impresso o valor de n na tela. Para saber o valor de n, o computador desempilha (pega o topo da pilha, o último elemento inserido na pilha) e obtém o valor 1.

pilha: 3, 2
saída: 0 1

Após imprimir o valor n, o procedimento imprimir e finalizado. Contudo, ainda existem chamadas empilhadas. Mais uma é desempilhada, onde o valor de n é 2. Assim temos:

pilha: 3
saída: 0 1 2

Após imprimir o valor n, o procedimento imprimir e finalizado. Contudo, ainda existem chamadas empilhadas. Mais uma é desempilhada, onde o valor de n é 3. Assim temos:

pilha:
saída: 0 1 2 3

Agora, percebe que a pilha de recursão está vazia, isso significa que acabaram as chamadas recursivas que haviam sido feitas. Finalizando o procedimento imprimir a execução do nosso programa volta lá para a função main, onde foi feita a chamada ao procedimento imprimir.

Código completo

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

void imprimir(int n){
    if(n == 0)
        printf("%d ", n);
    else{
        /* Retire o comentário do primeiro printf e teste o programa
        */ Depois comente o primeiro printf e retire o comentário do segundo printf e teste novamente.
        */ Avalie a diferença entre imprimir e fazer a chamada recursiva versus fazer a chamada recursiva e depois imprimir.
        */
        //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;
}