Linked List insert (implementing recursion)

[dolfan55aj]

I'm a new member and this is my first post, so be gentle ;)

It's been a while since I've gotten a chance to practice with recursion so to say I'm a bit rusty is an understatement. Not to mention I've never implemented it with a linked list. My current problem is transforming an iterative INSERT function for a linked list into a recursive function without changing the driver.

The following is my iterative function.

NodeType<ItemType> *nodePTR, *traverse;

	traverse = head;
	if(head == NULL)
	{
		head = new NodeType<ItemType>(item);
		length++;
		return true;
	}
	else
	{
		while(traverse != NULL)
		{
			if(traverse->info == item)
			{
				return false;
			}
			traverse = traverse->next;
		}
		nodePTR = new NodeType<ItemType>(item);
		nodePTR->next = head;
		head = nodePTR;
		length++;
          }
          return true;
	}

I'm mostly confused about the actual traversal of the list and simple insertion before I worry about the check. Any help is greatly appreciated, I'm sure it's partially a problem with my own mental logic. I'm unfortunately operating on a somewhat basic level.

If any other threads could be referenced that help with general linked list-recursion techniques that too would be appreciated (I did not see any that helped me much).

[mike_2000_17]

Turning a loop into a recursion is pretty simple: the body of the loop becomes the function body, and the loop-variable becomes the parameter passed from one recursion to the next.

The loop you have is not the best to lead you into making it a recursion, may I suggest this alternative which is pretty easy to turn into a recursion:

NodeType<ItemType>* traverse = head;
  while(true) {
    if( traverse == NULL ) {
      NodeType<ItemType>* nodePTR = new NodeType<ItemType>(item);
      nodePTR->next = head;
      head = nodePTR;
      length++;
      return true;
    } else if( traverse->info == item ) {
      return false;
    } 
    traverse = traverse->next;
  }

Turning the above into a recursion should be a piece of cake, with those two hints given above.