This is the hash table struct

struct hash_table
{
  entry_t buckets[No_Buckets];
};

This is the entry struct

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

What the function is meant to do is return the size of a hash table (how many !NULL entries it contains) but I am not sure how I should go about writing it recursively.

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;
}

CodePudding user response：

To answer your question, recursion generally means that the currently active function calls itself with varying parameters.

So, if you wanted to implement the above loop as recursive function, it'd be something like this:

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

This function takes the array of entries (hence the *), checks whether the first entry has a follow up item and then calls itself with the next item in line.

As I said in the comments though, 'the loop does the job just fine'. As a side note, passing the condition is necessary, because otherwise you'd run into 'infinite recursion', making your program crash.

On a side note, if you wanted to count the members of a linked list instead, the code would need to change like this:

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;
}

Or, if you REALLY wanted to do it recursively:

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

    return counter;
}