Recursive solution to counting nodes in a linked list

[kyleg033]

I know the iterative solution is the best way to go, but just to get a some more practice/experience with recursion how would you make a recursive solution to counting nodes in a linked list?

[kbw]

Have you tried it?
http://www.cplusplus.com/forum/articles/1295/

[kyleg033]

yes I have, I have had the base case as when current->next = NULL, but im really unsure of how to make a function that continues to call itself untill it gets to this base case. Some help would be great, im just really new to recursion!

[kyleg033]

Does anybody know how to do this?

[kbw]

You need to think about the problem in a particular way and identify what do you want to keep doing (recursively) and how do you know when to stop.

I feel like I'm doing your homework here, but if it helps you learn recursion then I'll try not to feel too bad about it.

#include <iostream>

struct Node
{
        Node* next;
        int payload;
};

Node* head = 0;

int count(Node* p)
{
        if (!p)
                return 0;
        if (!p->next)
                return 1;

        return 1 + count(p->next);
}

int main()
{
        head = new Node;
        head->next = new Node;
        head->next->next = new Node;

        int n = count(head);
        std::cout << n << std::endl;

        return 0;
}

[kyleg033]

Thanks buddy, oh its not homework if it makes you feel better!

[kyleg033]

public int length (LN 1)
  {
    if (l == null)
      return 0;
      else
      return 1 + length(l.next);
  }

This is what I came up with, so I think I'm on the right track!

[kbw]

That'll do, and it's even shorter than mine.