Recursion

[blackhawk9876]

I am having trouble writing these recursive functions. I know I am on the right track, but also know that these functions are not right. Any help would be appreciated.

Given the following declarations for a linked list:

struct NodeType;
struct NodeType { 
    int info; 
    NodeType* link; 
};

typedef NodeType* NodePtr;

2.1. Write a recursive value-returning function Search that searches a dynamic linked list for the integer value key. If the value is in the list, the function should return a pointer to the node where it was found. If the value is not in the list, the function should return NULL.

NodePtr Search(NodePtr head, int key)  { 
    ... 
}

2.2. Write a recursive value-returning function FindMax that returns the maximum value in a dynamic linked list of integers.

int FindMax(NodePtr head) { 
    ... 
}

this is what I have so far
for 2.1

NodePtr Search( NodePtr head, key)
{
NodePtr current;
current=head;

if(current==NULL)
{
return NULL;
}

while(current!=NULL)
{
  if(current->info==key)
{
return current->info;
}

 while(current->info!=key)
{
 Search (head->link);
}

}

for 2.2

int FindMax (NodePtr head)
{
NodePtr current;
current=head;

int value;

if(current==NULL)
{
return NULL;
}

while(current!=NULL)
{
 if(current->info > current->link->info)
value=current->info;

else
value=current->link->info;

FindMax(head->info);
}
}

[Narue]

>2.1. Write a recursive value-returning function that searches a linked list
>2.2. Write a recursive value-returning function that returns the maximum value in a linked list
"Recursive" and "linked list" are generally not terms that should be used in the same sentence. A linked list is normally a linear structure, and recursion isn't well suited to anything linear because there's a strong risk of stack overflow. When you use recursion, each new recursive call should simplify the problem approximately by half.

Besides, the non-recursive code is just as trivial for a linked list.

I know that's not helpful to your immediate problem, but I'm a bit pressed for time at the moment, so you'll have to wait until I'm more free.

[boblied]

Couple o' things:

Search has to return a pointer, so don't return info, return the pointer of the node you're looking at.

The recursive call of Search() has to take the same parameters as the first call, so don't forget to pass key.

That while loop at the end of search is trouble: if the condition wasn't true before calling Search(), it
still won't be true after you call search -- infinite loop. A simple if would do -- the recursion is taking the place of looping.

In FindMax, it would probably be helpful to pass the biggest value found so far as an input parameter.

[siddhant3s]

You have not written a recursive function.
Loosely speaking, Recursive functions should imply removal of ugly loops. I shall rather guide you in your first function.
You are using while to check an condition rather than if. This is unlikely (and maybe wrong too) by your instructor.
Here is a quick TODO for the first function:

START
* Check if Head is NULL; if it is return some value(preferably  zero) indicating failure of search
* Check if Head-info==key; if it is, return head
if it is not, call search(head->link,key)
END

All the checks are to be made be if's and not while. The idea is not to use loops.

[blackhawk9876]

Are these correct?

NodePtr Search( NodePtr head, key)
{

if(head==NULL)
{
return 0 ; 
}

While(head!=NULL)
{
if (head->info==key)
return head;
else
Search(head->link, key);
}
}

Does the above code answer "If the value is not in the list, the function should return NULL."

int FindMax (NodePtr head)
{
int value;

if(head==NULL)
{
return 0;
}

while(head!=NULL)
{
 if(head->info > head->link->info)
 	value=head->info;

else
	value=head->link->info;

	FindMax(head->link->info==value);
}
}

I know to the guy that posted above me not to use while statements but that is how she showed us, so I do not want change things around. Thank you for all who helped so far:)

[siddhant3s]

Listen Kid, Recursion = avoiding loop.
I don't know why your instructor told you to use loop in a recursive function.
the while loop your using is doing all the trouble. It is making your function a junk.
Your code (for Search) is absolutely fine if you remove the while loop:

//corrected version. Loop removed
NodePtr Search( NodePtr head, key)
{
if(head==NULL)
{
return 0 ; 
}
if (head->info==key)
return head;
else
Search(head->link, key);
}

Now do the needful for FindMax yourself.