Doubly Linked List show item HELP!

[alex067]

So in my program, I have created a grocery list with the main variables being the name of the item and the quantity.

I have to create a recursive function that tries to find a specific name of an item in the list.

So if user wants to see if Apples are in the list, the recursive function will check if the current pointer->name == itemName, then returns true, else it will move the pointer to the next node in the list and recall the function.

The problem arises when it turns back the truth value, it keeps just saying
"Checking if Apples is in the list"

But what should happen is, a truth value is returned from the recursive function, and then it should say:
"Apples is found!"

the function call is:
two.("Apples");

void GroceryList::lookup(string itemName) const
{
	ItemType * current = head;
	bool found;
	found = check(itemName, current);
	if (found == true)
	{
		cout << itemName << " found!" << endl;
	}
	if (found == false)
	{
		cout << itemName << " not in the list! " << endl;
	}
}

bool GroceryList::check(string itemName, ItemType * &x) const
{
	if (x->name == itemName)
	{
		return true;
	}
	else
	{
		goNext(x);
		if (x->next == NULL)
		{
			return false;
		}
		else 
		check(itemName, x);
	}
}

void GroceryList::goNext(ItemType * & curr) const //advances pointer to point to the next item
{
	curr = curr->next;
}

[alex067]

help please

[Ganado]

First, I don't think you should call goNext() before you check if x->next is null.

Let's say the list is {"a"}
User calls: check("c", current)
"a" != "c", so it then calls goNext, which makes current, I presume, be a null pointer, since you are already on the last element.
Then it dereferences this null pointer to make sure its next member variable is not NULL. I would make sure the next pointer is not null before you assign anything.


Second, I think that your check function's return calls don't necessary make it back to the original call, because you recursively call check(), but you don't return the value of it.
ex: make it return check(itemname, x);

_________
Maybe that makes sense? Let me know if you don't understand my poor wording.

[alex067]

I don't understand HOW it doesn't make it back.

Lets say the function calls itself twice, so current moves to the second node, and then current->name is Apple.

The first thing the function checks is if the name is Apple, if it is return true.


My program now works cause I added the return check, but I have another recursive function that doesn't use return, and it works??

Like this function works, and it doesn't use return

void GroceryList::printBackward() const
{
	ItemType * current = head;
	ItemType * temp = head; //acts as a place holder
	int count = 0;
	
	cout << "------ Grocery List (item:quantity) ------" << endl;
	if (isEmpty())
		cout << "You do not have any item.";

	while (current->next != NULL) //traverse to the very end of the node 
	{
		goNext(current); 
		count++;
	}
	//now current points to the last node, traverse backwards
	recurvBack(current, count);
	current = NULL;
	cout << endl;

}

void GroceryList::recurvBack(ItemType * &x, int size) const
{
	if (size == 0)
	{
		cout << "0)" << x->name << ": " << x->qty << endl;
		return;
	}
	else
	{
		cout << size << ")" << x->name << ": " << x->qty << endl;
		goPrevious(x);
		recurvBack(x, --size);
	}
}

[Ganado]

Not sure if that answers your question, but if it's a void function you wouldn't have any problem, because you don't need to worry about return values.

If we look at a simple recursive function:

bool r(int x)
{
    if (x <= 0)
        return true;
    else
        r(x - 1); // bad
}

The else branch makes a recursive call, but doesn't do anything with the return of this call. After that, it reaches the end of your r function.

The same thing happens in your code - you don't return the check call, so your logic gets out of the if-else statement, and gets to the end of your function, but there is no return at the end of your function, so it causes undefined behavior.

[dhayden]

Well your printBackward() function doesn't need to return a value since it's void. The problem with your original check() function is that, in the recursive case, it doesn't return anything, which means that the caller will read junk from for the return value.

By the way, you don't need to use goNext() at all:

bool GroceryList::check(cons string &itemName, ItemType *x) const
{
    if (x == NULL) {
	return false;
    } else if (x->name == itemName) {
	return true;
    } else {
	return check(itemName, x->next);
    }
}

Note that I've changed the arguments. itemName is a reference - no sense in making a new copy of the string for each call. x is now just a pointer. You don't want to change the value passed in.