How to count nodes of a link list by using Recursion in C++

Sign in to answer this question.

• 

  Vulpes12y agoPosted Sep 28, 2014, 7:08 AM

  Accepted answer

  To move through a 'standard' linked list in C++ we need an iterator and we also need to know when the iteration will end because there are no more nodes.
  
  So initially we pass the counter function a pointer to the first node and also a pointer to the position just after the last node.
  
  The total number of nodes is 1 plus the number of nodes from the next position to the end. So we increment the pointer and call the counter function recursively until eventually we get to the end when the stack unwinds and we're left with 0 plus a series of 1's which add up to the number of nodes in the linked list.
  
  
• 

  Joe Wilson12y agoPosted Sep 28, 2014, 2:45 AM

  Thank you for your answer and could you please explain this part of the project:
  I don't understand the codes below.
  

  int counter(list::iterator pos, list::iterator end)

  { 

     if(pos == end) return 0;

     return 1 + counter(++pos, end); // recursive call

  }
• 

  Vulpes12y agoPosted Sep 27, 2014, 3:42 PM

  Try this:
  
  

  #include

  #include

   

  using namespace std;

  
  

  int counter(list::iterator pos, list::iterator end)

  { 

     if(pos == end) return 0;

     return 1 + counter(++pos, end); // recursive call

  }

  
  

  int main()

  { 

     list numbers;

     list::iterator pos;

     int number, count, i;

     char lr;

  
  

     cout << "How many numbers are to be added to the linked list? : ";

     cin >> count;

     cout << "Enter them" << endl;

     for(i = 0; i < count; i++)

     {

        cout << i + 1 << " : ";

        cin >> number;

        numbers.push_back(number);

     }

  
  

     cout << endl;

  
  

     cout << "The numbers entered are" << endl;

     for (pos = numbers.begin(); pos != numbers.end(); pos++)

     {

        cout << *pos << " ";

     } 

  
  

     cout << endl << endl;

  
  

     int size = counter(numbers.begin(), numbers.end());

     cout << "There are " << size << " node(s) in the linked list";

   

     return 0;

  }