我怎么能递归地写这个函数？

Question

这是哈希 table 结构：

struct hash_table
{
  entry_t buckets[No_Buckets];
};

这是入口结构：

struct entry
{
  int key;       // holds the key
  char *value;   // holds the value
  entry_t *next; // points to the next entry (possibly NULL)
};

该函数的目的是 return 散列的大小 table （它包含多少个 !NULL 条目）但我不确定我应该如何递归地编写它.

int hash_table_size(hash_table_t *ht)
{
  int counter = 0;
  for (int i = 0; i < No_Buckets; i++)
  {
    entry_t *current_entry = (ht->buckets[i]).next;
    if (current_entry != NULL)
      {
        counter++ ;
      }
  }
  return counter;
}

Answer 1

为了回答您的问题，递归通常意味着当前活动的函数使用不同的参数调用自身。

所以，如果你想将上面的循环实现为递归函数，应该是这样的：

int countBuckets(struct entry *pEntry, int position)
{
     int count = 0;
     if (pEntry->next)
          ++count;
     if (++position < NoBuckets)
          count += countBuckets(++pEntry, position);
     return count;
}

此函数采用条目数组（因此是 *），检查第一个条目是否有后续项目，然后调用自身与行中的下一个项目。

正如我在评论中所说，'the loop does the job just fine'。作为旁注，传递条件是必要的，否则你会运行变成 'infinite recursion'，使你的程序崩溃。

附带说明一下，如果您想改为计算链表的成员数，则需要像这样更改代码：

struct hash_table
{
  entry_t *buckets;
};

int hash_table_size(hash_table_t *ht)
{
    entry_t *entry;
    int counter = 0;
    for (entry = ht->buckets; entry; entry->next)
        counter++ ;

    return counter;
}

或者，如果您真的想递归执行此操作：

int countBuckets(entry_t *entry)
{
    int counter = 0;
    if (entry)
        counter += countBuckets(entry->next) + 1;

    return counter;
}

我怎么能递归地写这个函数？

How could I write this function recursively?

c

recursion

struct

hashtable