2

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;
}
Improve this question
3
  • no, I just want to understand iterative to recursion conversion. I see lots of documents the other way round, but I tend to think in iterative manner, so just wanted to know if there is a fixed way to go about it and if yes then how to handle the base case. Thanks Commented Oct 29, 2011 at 14:34
  • @user1017072: you're already handling the base case in the iterative version. Commented Oct 29, 2011 at 14:39
  • yes Mat, but I want to see its recursive version to understand the overhead. Thanks Commented Oct 29, 2011 at 14:42

5 Answers 5

Reset to default
4

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));
}
Improve this answer
Sign up to request clarification or add additional context in comments.

5 Comments

Hi Ben thank you for the reply, I am sorry to bother you, but could you help me in understanding what the last two lines are doing in the code: if(current->next == start) return c; return (c + count_helper(current->next, start)); Thank you very much for your help.
if (current->next == start) return c; is the terminating condition for when you hit the loop re-entry point.
return (c + count_helper(current->next, start)); takes the current value of c and performs a tail recursion on the remaining part of the loop. Try it out with a small loop and step through it.
@BenHocking: I don't think c + count_helper(current->next, start) is technically tail recursive. It has to store c in each stack frame (unless the optimiser is smart enough to deal with that, which it likely is).
Thank you very much for all the help Ben and Mange.
1 
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;
}
Improve this answer

9 Comments

The list is circular (I made the same mistake at first).
Well: don't make it circular, than ;-) (why is this not in the title?) I'll try to update my snippet... BTW: it is a double linked list, too.
@wildplasser, sorry for not mentioning circular and doubly linked list in the title. For some reason, the code leaves out counting the first node if it has 20.
No, it does recurse if ptr->roll_no == 20; there are prentheses. But it fails to count the last node. I'll update. again.
Off course you can. It all depends on your typical usage of the datastructure. You could even maintain a counter that is incremented every time a node with (ptr->roll_no == 20) is inserted (and decremented, etc) Or you could keep two lists, or a tree or whatever. It all depends on what you want to do. BTW a LL is a rather unpractical datastructure. A cyclic LL is seen very rarely. I think I never saw one in my 20+ years of programming (and reading programs).
|
1 
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.

Improve this answer

3 Comments

Hi mange, I was just going through your tail recursive solution to understand the benefits. The program seems to return 0, no matter how many nodes have 20 in them. I am guessing it has some issue with parameter c. Thanks
Did you put the c+1 in the if (current->roll_no == 20) instead of just c? The general idea is that instead of using named variables you pass through the variables as arguments to the next function, so instead of c = c+1, you pass c+1 as the c argument of the next function call.
Ah, I've just realised that this actually doesn't work at all because I'm stupid. Fixing it now. (I wasn't testing the start properly, so it terminated immediately.)
0

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.

Improve this answer

Comments

0

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

Improve this answer

1 Comment

Your code returns always 0, Did you mean return count(start, start->next, &countValue);

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.