Dando continuidade ao nosso Curso de Programação C, vamos ver uma aplicação da estrutura pilha. Vamos ver nesta aula como simular a recursão com uma estrutura de dados PILHA.

O fatorial é por definição recursivo, como vimos na aula 155. Contudo, é possível calcular o fatorial de um número n sem utilizar recursão. Neste exercício vamos utilizar uma pilha. A ideia é, enquanto n for maior que 1, vamos empilhar o valor de n e subtrair 1.

Imagine que n seja 3, vamos empilhar o 3 e depois o 2. Neste momento, como n vale 1 e sabemos o fatorial de 1, iniciamos o processo inverso, desempilhando e multiplicando. Quando a pilha estiver vazia teremos o fatorial de n. A função abaixo calcula e retorna o fatorial de um número exatamente com esta lógica. Perceba que a nossa estrutura pilha está dentro da função fatorial e não mais na função main.

/*
   função para calcular o fatorial por meio de uma pilha
*/
int fatorial(int num){
    No *remover, *pilha = NULL;

    while(num > 1){
        pilha = empilhar(pilha, num);
        num--;
    }
    // aqui num vale 1
    imprimir(pilha);

    while(pilha){
        remover = desempilhar(&pilha);
        num = num * remover->valor;
        free(remover);
    }
    return num;
}

Código completo em C para calcular o fatorial de um número com uma estrutura de dados pilha

/*
            Aula 229: Como simular a recursão do fatorial com uma pilha?

            Código escrito por Wagner Gaspar
            Julho de 2021
*/

typedef struct no{
    int valor;
    struct no *proximo;
}No;

No* empilhar(No *pilha, int num){
    No *novo = malloc(sizeof(No));

    if(novo){
        novo->valor = num;
        novo->proximo = pilha;
        return novo;
    }
    else
        printf("Erro ao alocar memoria!\n");
    return NULL;
}

No* desempilhar(No **pilha){
    No *remover = NULL;

    if(*pilha){
        remover = *pilha;
        *pilha = remover->proximo;
    }
    else
        printf("Pilha vazia!\n");
    return remover;
}

void imprimir(No *pilha){
    printf("\n\tPILHA\n");
    while(pilha){
        printf("\t%d\n", pilha->valor);
        pilha = pilha->proximo;
    }
    printf("\n");
}

// função para calcular o fatorial por meio de uma pilha
int fatorial(int num){
    No *remover, *pilha = NULL;

    while(num > 1){
        pilha = empilhar(pilha, num);
        num--;
    }

    imprimir(pilha);

    while(pilha){
        remover = desempilhar(&pilha);
        num = num * remover->valor;
        free(remover);
    }
    return num;
}

int main(){
    int valor;

    printf("Digite um valor maior que zero para o fatorial: ");
    scanf("%d", &valor);
    printf("\tFatorial de %d: %d\n", valor, fatorial(valor));

}