Recentemente encontrei um usuário no Reddit pedindo pra resolver uma questão sobre análise combinatória em C utilizando recursão. O exercício pedia que fosse feito um programa em C que exibisse no terminal todas as combinações possíveis de três caracteres, utilizando as letras a, b e c.

É um exercício clássico de recursividade, mas é muito bom pra ir além de calcular o fatorial.

Vamos começar declarando a função:

void print_combination(int size, char *comb);

O segundo parâmetro vai ser utilizado para executar a recursividade, a chamada inicial tem que usar NULL.

Condição Inicial

Em seguida vamos definir a condição inicial, prepara tudo pra executar a função, utilizando o segundo parâmetro como referência

if (!comb) {
    if (!(comb = (char*)malloc(size + 1))
        return;
    comb[0] = '\x0';
    print_combinations(size, comb);
    free(comb);
    return;
}

A memória é alocada na primeira execução, e não recursivamente. Sempre evite alocar memória recursivamente, o consumo de memória pode crescer exponencialmente, saindo do controle rapidamente.

Outro detalhe importante: se a função aloca memória, ela própria tem que desalocar. Além disso a memória não é alocada recursivamente, evite ao máximo alocar memória recursivamente, o consumo de memória pode crescer exponencialmente, saindo do controle rapidamente.

Recursividade

A recursão ocorre a cada letra adicionada na sequência, dessa forma:

int cursize = strlen(comb);
comb[cursize + 1] = '\x0';
for (int ct = 'a'; ct <= 'c'; ct++) {
    comb[cursize] = ct;s
    print_combinations(size, comb);
}
comb[cursize] = '\x0';

Assim, para cada letra de a a c, aumentamos o tamanho da sequência adicionando uma letra a mais. Note o cuidado de voltar a sequencia para o estado anterior ao final do loop.

Condição de Parada

Agora a condição de parada. Em recursividade é necessário sempre ter uma condição de parada:

if (cursize == size) {
    printf("%s\n", comb);
    return;
}

Quando a sequência alcançar a quantidade necessária de letras, basta imprimi-la.

O Programa

Montando o programa inteiro, todo junto, incluindo linha de comando vamos ter o seguinte arquivo combinations.c

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

void print_combinations(int size, char* comb) {    
    // initial condition
    if (!comb) {
        if (!(comb = (char*)malloc(size + 1)))
            return;
        comb[0] = '\x0';
        print_combinations(size, comb);
        free(comb);
        return;
    }

    int cursize = strlen(comb);

    // stop condition
    if (cursize == size) {
        printf("%s\n", comb);
        return;
    }

    // recursion
    comb[cursize + 1] = '\x0';
    for (int ct = 'a'; ct <= 'c'; ct++) {
        comb[cursize] = ct;
        print_combinations(size, comb);
    }
    comb[cursize] = '\x0';
}

int main(int argc, char* argv[]) {
    if (argc < 2) {
        printf("Usage:\n");
        printf("\tcombinations <COMBINATION SIZE>");
        return 1;
    }

    int size = atoi(argv[1]);
    print_combinations(size, NULL);
    return 0;
}

Profissionalmente

Um detalhe muito importante nessa solução, em algumas equipes recursividade deve ser evitada, ou passar por uma avaliação muito criteriosa, pois pode causar danos consideráveis ao consumo de memória do sistema.

Apesar de aparecer um exercício banal, é relativamente comum precisar utilizar força bruta para resolver alguns problemas. Às vezes é necessário levantar todas as possibilidades aceitáveis antes de decidir qual é a mais viável, e um computador, com sua grande capacidade de repetição é o mais apropriado para fazer tal tarefa.

Muito cuidado com alguns detalhes encontrados no código

• Desaloque a memória dentro da própria função – evite deixar a memória para o usuário da função desalocá-la. E quando for necessário não desalocar, forneça funções para desalocação apropriada.
• Verifique a memória alocada – nem sempre o sistema pode alocar toda a memória necessária, para evitar falhas de memória, com consequencias que podem ser graves, sempre verifique a alocação.
• Falhe o mais rapidamente possível – note que a condição final foi verificada antes da recursão, sempre que possível coloque as condições de saída de uma função antes do resto do processamento.

EDIT: Muito obrigado a Joilnen Leite, por apontar uma pequena falha no programa.

Tags: c, recursividade