Conceptual recursion question

[hopesfall]

Let's say I have a list of items (any kind, but I'll use strings here) and I want to create a recursive function that tells me where in the list an item is. My list is connected by pointers that point to the next node(each object in the list), with the last node pointing to NULL, and the first node being pointed to by an independent "head" pointer. How could I create a recursive method that tells me where in the list (at what position, maybe an index?) my item is?

This is an assignment for my class and he gave us the prototype for the function:
int recursiveLocatePosition(ListNode * const & within, const ListItemType & lookFor, bool & isPresent) const;

The only way I've thought about doing this is with a counter that counts as I get deeper into the recursion, but my prof. told me that's not the right way of thinking about it.

[ciphermagi]

It looks like he's trying to make you design an iterator. What you want to do is design a function that returns a pointer independent of the list completely that can redirect users to a specific element of the list without having any effect on the other members of the list.

[Disch]

The only way I've thought about doing this is with a counter that counts as I get deeper into the recursion, but my prof. told me that's not the right way of thinking about it.

You basically have the right idea. You don't need an actual counter variable though. The return value acts as the counter, and it gets larger and larger the further into the recursion you get.

I think your professor was steering you away from this kind of thing, which is NOT what you want to do:

int count = 0;

int locate(...)
{
  ...
  if( didnt_find )
    ++count;
}

But the idea of a counter is kind of right. Just use the return value as the counter.

EDIT:

ciphermagi wrote:

It looks like he's trying to make you design an iterator.

But how would an iterator help you find the numerical position?

[hopesfall]

I'm still having troubles wrapping my head around this....Can anyone explain more? Here's what I have so far:

int List::recursiveLocatePosition(ListNode * const & within, const ListItemType & lookFor, bool & isPresent) const{
		
		ListNode *newPtr = new ListNode;
		newPtr = within;

		if(within == NULL){
			isPresent = false;
			throw ListException(
			"ListException: Item doesn't exist.");
		}
		else if(within->item == lookFor){
			isPresent = true;
		}
		else{
			newPtr = within->next;
		    
			recursiveLocatePosition(newPtr,lookFor,isPresent);
		}
		return WHAT_GOES_HERE??;
	}

[Disch]

You're close.

Thinking in recursion is a little weird.

Think of the pattern:

if the item is found in the first node, you return 0
if the item is found in the second node, you return 1
third node, you return 2

right? So.... to look at that recursively, you need to think in terms of "this" node.


So the node after this node would be +1. The node 2 after this node would be +2 (or... the node after the node after this node would be +1+1)

[viliml]

I'm not sure how your class works, and I don't know much about recursions, but i think ths might work:

int List::recursiveLocatePosition(const ListNode* &within=/*first element*/, const ListItemType& lookFor, bool& isPresent, int counter=0) {

		ListNode *newPtr = new ListNode;
		if(within == NULL){
			isPresent = false;
			throw ListException(
			"ListException: Item doesn't exist.");
			return -1;
		}
		else if(within->item == lookFor){
			isPresent = true;
			return counter;
		}
		else{
			newPtr = within->next;
			return recursiveLocatePosition(newPtr,lookFor,isPresent,counter+1);
		}
	}

[viliml]

bump

[roberts]

		ListNode *newPtr = new ListNode;
		newPtr = within;

Doing this is going to be a memory leak, I believe. You're allocating memory that is the size of class ListNode, then assign it the address of within, so the memory you just allocated gets lost, but not deleted.


Guys, I don't think you should be redefining the function call and prototype. His professor gave him what he wants to see and have hopesfall use.

Think of the pattern:

if the item is found in the first node, you return 0
if the item is found in the second node, you return 1
third node, you return 2

So you think his prof is having him do a linear search of a linked list using recursion?

[zwA4jE8b]

try using the exit condition if(within->next == NULL || within->data == lookfor) that way the recursion breaks either at the end of the linked list for if you find what you are looking for.

const ListNode* &within //dont use the ampersand here

ListNode *newPtr = new ListNode; //remove this
...
newPtr = within->next;  //remove this line
return recursiveLocatePosition(within->next,lookFor,isPresent,counter+1);  //send it here, that way there is no new memory allocated
}

This code recursively goes through a linked list and searches for whatever value I sent 't', if it is found true is returned, else it keeps going

struct node
{
int value;
node* link;
};
bool member(node* l, int t)
{
	if(l->link != NULL)
		if(l->value == t) return true;
		else member(l->link, t);
	else return false;
}

[ne555]

if(l->link != NULL) ¿And why worry about a speck in your friend's eye when you have a log in your own?

[Disch]

do not pass a counter

The return value is the counter.

it's very simple:

if( found_in_this_node )
  return 0;
else
  return 1 + search_next_node(...);