Converting an iterative function to recursive

Question

I know people usually ask this question the other way round, but I have the following problem: I have this iterative function which counts all the nodes in a circular doubly link list containing the data value 20. Now, how do I make this recursive, what will be the base case (terminating case) for the recursive function? Any help is appreciated:

int count(node *start)
{
    int c;
    c = 0;
    if(start == NULL)
        return 0;
    if((start->roll_no) == 20)
        c = 1;
    node *current = start;
    while(current->next != start)
    {
        if((current->next->roll_no) == 20){
        c++;
        }
        current = current->next;
    }

    return c;
}

Answer 1

I think this should work (but note that it requires an extra argument for tracking start):

int count(node *start)
{
    return count_helper(start, start);
}
int count_helper(node *current, node *start)
{
    int c;
    c = 0;
    if(current == NULL)
        return 0;
    if((current->roll_no) == 20)
        c = 1;
    if(current->next == start) return c;
    return (c + count_helper(current->next, start));
}

Answer 2

int count_recursive (node* current, node* start) {
  if (current == NULL)
    return 0;
  if (current->next == start)
    return (current->roll_no == 20 ? 1 : 0);
  if (current->roll_no == 20)
    return count_recursive(current->next, start) + 1;
  else
    return count_recursive(current->next, start);
}
int count(node* start) {
  return count_recursive(start, start);
}

The base case is "the list is empty" or "we are at the end of the list". Then you recurse by taking the rest of the list (without the item we just looked at) and doing the exact same thing.

Note that this is not tail recursive (although it may get optimised into a tail recursive option), so it will grow the stack and may explode.

Tail recursively:

int count_recursive (node* current, node* start, int c) {
  if (current == NULL)
    return c;
  if (current->next == start)
    return (current->roll_no == 20 ? 1 : 0) + c;
  if (current->roll_no == 20)
    return count_recursive(current->next, start, c+1);
  else
    return count_recursive(current->next, start, c);
}
int count(node* start) {
  return count_recursive(start, start, 0);
}

The tail recursive option is more likely to be optimised into a loop by the compiler, but a sufficiently intelligent compiler should turn them both into a loop.

Answer 3

int count(struct node * ptr)
{
    return ptr==NULL ? 0 : (ptr->roll_no == 20 ? 1:0) + count(ptr->next);
}

UPDATE: it appears the list is circular.

int count(struct node * start, struct node * ptr)
{
    return ptr==NULL || ptr->next == start ? 0 
                                           : (ptr->roll_no == 20 ? 1:0) 
                                             + count(start, ptr->next);
}
/* to be called like: */
cnt = count (the_list, the_list);

UPDATE 2: (failure to count the last node)

int count(struct node * start, struct node * ptr)
{
    return ptr==NULL  ? 0 
                      : (ptr->roll_no == 20 ? 1:0) 
                        + ptr->next == start ? 0
                                             : count(start, ptr->next);
}

UPDATE3: it did need an extra pair of parentheses...

#include <stdio.h>

struct node {
        struct node *next;
        int roll_no;
        };

struct node nodes[8] =
{{ nodes+1, 20} ,{ nodes+2, 0}
,{ nodes+3, 20} ,{ nodes+4, 0}
,{ nodes+5, 20} ,{ nodes+6, 0}
,{ nodes+7, 20} ,{ nodes+0, 0}
};

unsigned count(struct node * start, struct node * ptr)
{
    return ptr==NULL
              ? 0
              : (ptr->roll_no == 20 ? 1:0)
                + (ptr->next == start
                    ? 0
                    : count(start, ptr->next)
                  )
              ;
}

#define COUNT(p) count(p,p)

int main (void)
{
unsigned cnt,idx;

for (idx = 0; idx < 8 ; idx++) {
    cnt = COUNT (nodes+idx);
    printf ("count@%u = %u\n", idx, cnt);
    }

return 0;
}

Answer 4

There is no making this recursive, because there is no recursion in the structure, it is already a list.

Usually, because recursion has a lot of overhead, you can rewrite such a function to iterative, by creating a list (or stack) of 'levels to do'. Instead of recursively calling the function, you can push the item on the stack, and loop your routine until the stack is empty.

An example is listing a file tree. Instead of calling the function recursively for each found directory, you can also push the directory name on a stack of directories to process. That way, you don't have a large number of directory handles or iterators or whatever you're using, when you have a deeply nested tree.

But none of that applies here, since you don't have a tree at all.

It can be done, though: You could replace the while with a recursive call, but you would have to pass the original start, or make it global, or else you wouldn't know when to break the recursion. Also, though possible, you will get it trouble soon if you got a long list.

Answer 5

How about this :

int count(node *start){  
   if(!start) return 0;  
   int countValue = 0; 
   return count(start,start,&countValue);
}


int count(node *start, node *next, int *count){  
    if(start == next)//circular list so this is your base
       return *count;
    if(next->next->roll_no) == 20){  
         *count++;
    }  
    return count(start,next->next,count);  
}

It is not custom for recursive functions to modify input params though.
Nor to use use global variable.
This is the first approach I could come up