Implemente uma rotina recursiva para calcular o tamanho de uma lista dinâmica e encadeada.

Passo 1

O enunciado pede para criarmos uma função recursiva que, dado o ponteiro para o primeiro nó de uma lista simplesmente encadeada, retorne quantos nós existem nessa lista. O conteúdo aqui é recursão aplicada a estruturas de dados (listas ligadas).

Passo 2

Primeiro, precisamos de uma definição de nó da lista. Em C, por exemplo, usamos uma struct que contém um campo de dado (podendo ser um inteiro, float, etc.) e um ponteiro para o próximo nó. Essa definição é fundamental para entendermos o que a função vai percorrer.
A ideia da recursão é identificar o caso base e o passo recursivo. Caso base: quando o ponteiro passado for NULL, significa que chegamos ao fim da lista e não há mais elementos, então retornamos 0. Passo recursivo: se o ponteiro não for NULL, retornamos 1 (contando o nó atual) mais o resultado da chamada recursiva para o próximo nó.

Passo 3

Implementamos a função seguindo a lógica acima. Cada chamada conta o nó atual e delega ao subproblema (lista sem o primeiro nó). Quando chegamos a NULL, a recursão termina.
Com a função pronta, basta chamá-la passando o ponteiro para a cabeça da lista. Ela retornará um inteiro com o tamanho total da lista.

Resposta

// Definição do nó da lista
typedef struct Node {
int data;
struct Node *next;
} Node;
// Função recursiva que retorna o tamanho da lista
int tamanhoLista(Node *head) {
// Caso base: lista vazia
if (head == NULL) {
return 0;
}
// Passo recursivo: 1 (este nó) + tamanho do restante
return 1 + tamanhoLista(head->next);
}
/*
Exemplo de uso:
Node lista = / … montar lista dinâmica … */;
int n = tamanhoLista(lista);
printf(“Tamanho da lista: %d\n”, n);
*/

Exercícios relacionados