Linked list and recursion

[Ami_01]

Hello programmers ,


I have to develope a recursive function in C.


Given a linked list and node:

First --> [7][ ] --> [23] [ ] --> [9] [ ] --> [43] [ ] --> [51] [•]

Typdef  struct node {
            Unsigned data;
   	Struct  node *next;
} node

I have now to write a recursive function Minimum() wich returns smallest data element. (so smallest data element from node).

Please can anybody help me???

Thanx in advance from Holland

[quzah]

What's your attempt at it? Let's see your code or pseudo code of how you think it should work.


Quzah.

[Ami_01]

I think I have it, but not recursive
I must have it recursive

int MinList (NodePtr theList) {
  int min = theList -> data;		//set minimum to first data
  NodePtr currNodePtr = theList->next; //set pointer to next node
  
  while(currNodePtr != NULL) {
    if(currNodePtr->data < min) {
      min = currNodePtr-> data;
    } //if current data is less than current min
    
    currNodePtr = currNodePtr -> next;	//move to next node
  }
  return min;
}

[quzah]

To make a recursive method, you first need a way to stop recursion. Check the passed argument's 'next' pointer to see if it's null. If it is, stop with this comparison. If it's not, pass it along.

Next, you need to do a comparison with this node's value compared to what is returned by the recursive call. Return which ever of the two is greater. That should get you started. (And finished.)


Quzah.

[Ami_01]

Hi Quzah or other programmers,

Can you help me more pls.
I now have the following:

unsigned Miniumum(node **n,int number) {
       if (*n  != NULL)  
              return number;
       else return Minimum(&(*n)->next,number)
}

But I think it is not good.
My function prototype should be:

unsigned Minimum(node **n);

Help me pls more,

thanx in advance from Holland

[xErath]

ignore that function - it's indeed bad.
Think of the following
if current node is NULL stop
for each iteration store the smaller number and the current number.
if smaller> current .. bla bla bla
pass next node to function.

of course this should be better if done inside a cicle. Function calls are much less efficient than a single cicle.

[Ami_01]

Hi xErath or other people,

xErath thanx for message.
When I understand you good, you mean:

unsigned Min(node *n) {
   unsigned min;

   if (n == NULL)
       return NULL;
   else if (min < n->data) {
       min = n->data;
       return  Min(&n->next);
   }
}

Help me if I am wrong. I am thinking of initialising min????

Thanx in advance everybody

Holland

[dwks]

You might try using static.

Here's how I would do it:

unsigned min(node *n) {
    unsigned other;

    if(!n->next) return n->data;

    other = min(n->next);

    if(other < n->data) return other;
    else return n->data;
}

I think that might work.

[edit]
The above code assumes that n != NULL.
[/edit]

[Ami_01]

Thanx for your code dwks

Is this a right sollution?

Thanx for answer

[dwks]

dwks thinks so.

Ask quzah.

[quzah]

Why don't you just try it and find out?


Quzah.