如何将C语言哈希表元素计数函数改写为递归实现？

首先需要注意：你当前提供的迭代实现逻辑存在缺陷，它仅统计了每个桶的首个链表节点是否存在，没有遍历整条链表统计所有entry节点，不符合「统计所有非空entry总数量」的需求。我们先修正该逻辑，再通过两层递归实现需求：

• 第一层递归：遍历哈希表的所有桶
• 第二层递归：遍历单个桶下的entry链表，统计该桶的节点总数

完整实现代码 #

1. 链表计数递归辅助函数 #

负责递归统计单条entry链表的总节点数：

// 递归统计单条entry链表的节点总数
int count_entry_chain(entry_t *entry) {
    // 递归终止条件：当前节点为空，代表链表遍历结束
    if (entry == NULL) {
        return 0;
    }
    // 当前节点计数1 + 后续链表的节点总数
    return 1 + count_entry_chain(entry->next);
}

2. 桶遍历递归辅助函数 #

负责递归遍历所有哈希桶，累加每个桶的entry总数：

// 递归遍历下标从index到No_Buckets-1的所有桶，统计总entry数
int count_buckets(hash_table_t *ht, int index) {
    // 递归终止条件：下标超过最大桶编号，代表所有桶遍历结束
    if (index >= No_Buckets) {
        return 0;
    }
    // 当前桶的entry数 + 后续所有桶的总entry数
    return count_entry_chain(ht->buckets[index].next) + count_buckets(ht, index + 1);
}

3. 对外暴露的hash_table_size实现 #

int hash_table_size(hash_table_t *ht) {
    // 非法参数校验（可选）
    if (ht == NULL) {
        return 0;
    }
    // 从第0个桶开始递归遍历
    return count_buckets(ht, 0);
}

内容的提问来源于stack exchange，提问作者fireproofiii