Para fechar esta unidade sobre listas encadeadas, vamos olhar para elas sob uma perspectiva diferente: uma lista encadeada é, por natureza, uma estrutura recursiva. Veremos como isso permite reescrever as operações vistas na Aula 4 usando recursão em vez de laços.

1. Por que uma lista é recursiva?

Lembrando a Aula 4: uma lista simplesmente encadeada representada por Nodo *lista é sempre uma destas duas coisas:

• a lista vazia (lista == NULL); ou
• um nodo, contendo um dado e um ponteiro prox que é, ele mesmo, o início de outra lista (menor).

Essa definição é praticamente idêntica à ideia de recursão vista no laboratório de revisão de linguagem C (Material Extra, contarAprovados): um caso base (a lista vazia) e um caso recursivo (um nodo mais uma lista menor). Isso sugere que qualquer operação sobre listas pode ser escrita de forma recursiva, tratando o prox de um nodo como "o restante da lista".

2. Operações recursivas sobre listas

tamanho

Comparando com a versão iterativa da Aula 4:

// Versão iterativa (Aula 4)
int tamanho(Nodo *lista) {
    Nodo *aux = lista;
    int contador = 0;

    while (aux != NULL) {
        contador++;
        aux = aux->prox;
    }

    return contador;
}

// Versão recursiva
int tamanho(Nodo *lista) {
    if (lista == NULL) // caso base: lista vazia tem tamanho 0
        return 0;

    return 1 + tamanho(lista->prox); // caso recursivo: 1 (este nodo) + o restante
}

imprime

void imprime(Nodo *lista) {
    if (lista == NULL) // caso base: nada a imprimir
        return;

    printf("%d - %s - %.2f\n", lista->dado.cod, lista->dado.nome, lista->dado.preco);
    imprime(lista->prox); // caso recursivo: imprime o restante da lista
}

consulta

Produto consulta(Nodo *lista, int cod) {
    Produto prod = {-1, "", 0.0f};

    if (lista == NULL) // caso base: não encontrado
        return prod;

    if (lista->dado.cod == cod) // caso base: encontrado neste nodo
        return lista->dado;

    return consulta(lista->prox, cod); // caso recursivo: procura no restante
}

insereInicio

Inserir no início não é realmente "recursivo" (o novo nodo não depende do restante da lista para ser calculado), mas se encaixa perfeitamente na definição: a nova lista é um nodo cujo prox é a lista inteira anterior:

Nodo* insereInicio(Nodo *lista, Produto prod) {
    Nodo *novo = (Nodo*) malloc(sizeof(Nodo));
    if (novo == NULL)
        return lista;

    novo->dado = prod;
    novo->prox = lista; // o restante da lista, sem nenhuma alteração
    return novo;
}

destroi

Este é o caso mais interessante: para destruir a lista, primeiro destruímos o restante (recursivamente) e só depois liberamos o nodo atual — a ordem importa, pois precisamos do ponteiro prox ainda válido para poder chamar a recursão antes do free():

Nodo* destroi(Nodo *lista) {
    if (lista == NULL) // caso base: nada a destruir
        return NULL;

    destroi(lista->prox); // destrói o restante primeiro
    free(lista);
    return NULL;
}

3. O custo escondido da recursão

As versões recursivas costumam ser mais curtas e, para quem já entende a definição recursiva de lista, mais diretas de ler. Mas elas têm um custo que não aparece na complexidade Big-O: relembrando o Material Extra — Conceitos de Linguagens de Programação, cada chamada recursiva empilha um novo quadro de ativação na pilha.

Para uma lista com n elementos, uma função como tamanho ou destroi empilha n chamadas recursivas antes de começar a retornar. Se n for muito grande, isso pode esgotar o espaço da pilha, causando um stack overflow — exatamente o mesmo risco discutido no Material Extra — Conceitos de Linguagens de Programação para recursões profundas.

Resumo

Exercícios

1. Identifique o caso base e o caso recursivo da função consulta apresentada nesta aula.
2. Por que, na função destroi recursiva, é necessário chamar destroi(lista->prox) antes de free(lista), e não depois?
3. Explique por que a versão recursiva de tamanho consome O(n) de espaço na pilha, enquanto a versão iterativa consome apenas O(1), mesmo as duas tendo a mesma complexidade de tempo.
4. Implemente uma versão recursiva de int soma(Nodo *lista), que retorne a soma dos preços (arredondados para inteiro) de todos os produtos da lista.
5. Implemente uma versão recursiva de Nodo* insereFim(Nodo *lista, Produto prod). Dica: pense em qual é o caso base (lista vazia) e como a chamada recursiva deveria alterar apenas o prox do resultado retornado.

Sugestões de Respostas dos Exercícios

int soma(Nodo *lista) {
    if (lista == NULL) // caso base: lista vazia soma 0
        return 0;

    return (int) lista->dado.preco + soma(lista->prox); // este nodo + o restante
}

Nodo* insereFim(Nodo *lista, Produto prod) {
    if (lista == NULL) { // caso base: lista vazia, novo nodo é o único (e o fim)
        Nodo *novo = (Nodo*) malloc(sizeof(Nodo));
        if (novo == NULL)
            return NULL;

        novo->dado = prod;
        novo->prox = NULL;
        return novo;
    }

    // caso recursivo: mantém este nodo, insere no restante da lista
    lista->prox = insereFim(lista->prox, prod);
    return lista;
}