recursive function to use on linked list?

[dan_e6]

hey guys. ive been asked to do this:

Write a recursive function which returns true if the linked list is sorted in
ascending order.
bool isSorted(nodeType *L)

why would we use a recursive function to check if it's in ascending order? can anyone help me with this.

[VernonDozier]

hey guys. ive been asked to do this:

Write a recursive function which returns true if the linked list is sorted in ascending order. bool isSorted(nodeType *L)

why would we use a recursive function to check if it's in ascending order? can anyone help me with this.

If I were to write it, I doubt I would use recursion, though you certainly could use it. You could write it recursively very similarly to using a while loop:

while (L != NULL)
{
     if (some condition)
     {
          // return true or false
     }
     L = L->next;
}

// return true or false

The same logic can be tweaked for recursion. Get rid of the while loop. Every trip through the current while loop is a new call to the function. Your base condition to get out of infinite recursion is the same as your while loop condition.

[John A]

>why would we use a recursive function to check if it's in ascending order?

It's just another poor example of teachers trying to get students to use recursion. In most cases the solution to the assignment they hand out would be much better suited to a loop, and the result is that kids know how to use recursion, but don't know when to use it. Theoretically, any recursion can be turned into a loop, but situations do exist out there where recursion actually can provide a simpler solution -- it's just somewhat difficult for teachers to create assignments which demonstrate that.

Go with what VernonDozier suggested about doing it with a loop first, then adding recursion once you've got the loop working. It'll be much simpler to think that way.

[dan_e6]

im at a stump......

i need to declare a copy of the current linked list like so:

node *t = start_ptr;

and iterate through the linked list using this temporary linked list. but the thing is, if i declare the temp node t at the begining of the recursive function it will be RE-declared everytime i loop through.
how would i go about this?

[dan_e6]

okay here's wht ive got so far.

the node pointer is called start_ptr
ive also declared a global node pointer called current that is NULL to begin with.
this is my recursive function. it crashes though :(

void Library::sorted()
{
     
     if (current==NULL)
     {
        node *current = start_ptr;
     }

     if (! (current->next == NULL))
     {
        node *t = current->next;
        if (current->pdata->nAuthors > t->pdata->nAuthors)     
           {
                          cout << "List is not in order." << endl;
           }
           else
           {
               current = current->next;
               sorted();
           }           
        
     }
}

[dan_e6]

okay i fixed it and it works fine now.....

the problem was in the

if (current == NULL )

i needed to set current to start_ptr NOT re-declare it everytime!!!! now it works fine.

[hammerhead]

I dont think your code classifies as recursion. Neither does it satisfy the question
bool isSorted(nodeType *L)

This is what I would do to check if a link list is sorted using recursion

bool sorted(node *curr)
{
     if(curr->next==NULL)
     {
                   return true;
     }
     else if(curr->val>curr->next->val)
     {
          return false;
          }
          
          else
          {
              return sorted(curr->next);
           }
}

Note that there are two base cases.

[dan_e6]

ah yes i forgot to make it accept the node as a parameter. my bad.
but howcome my version didnt classify as recursion when it did indeed call the function inside itself?

PS: ,thanks for that, it made my code even shorter. i totally overlooked the fact that i didnt need to make a temp node. hehe.

[hammerhead]

>>but howcome my version didnt classify as recursion when it did indeed call the function inside itself?

I didn't think it did because it does not fall into the conventional definition of recursion.
http://www.nist.gov/dads/HTML/recursion.html

Your code did not have base cases, i.e. termination cases. And it did not combine the solution to get the integrated solution.

[dan_e6]

ah so this part of the definition:

"calls itself with some part of the task. "

is why my routine wouldnt be classified as recursive because it does call itself but it doesnt provide 'some part of the task' as a parameter. fair enough.

[n1337]

It's just another poor example of teachers trying to get students to use recursion. In most cases the solution to the assignment they hand out would be much better suited to a loop, and the result is that kids know how to use recursion, but don't know when to use it. Theoretically, any recursion can be turned into a loop, but situations do exist out there where recursion actually can provide a simpler solution -- it's just somewhat difficult for teachers to create assignments which demonstrate that.

It is difficult to create assignments on recursion in a conventional course because generally recursive solutions are best suited to more advanced data structures (braun trees, directed graphs, etc) which are likely beyond the scope of a first programming course...so you end up learning recursion just for the sake of satisfying the curriculum.

The issue is of course, once you've learned looping, recursion is given to you as an afterthought, and you become so entrenched in looping iterations that thinking recursively is much more difficult, and seemingly pointless. The other thing is, I don't believe that any C++ compiler optimizes for structural or mutual recursion, only tail recursion for speed reasons (i.e. on a standard C++ compiler, structural/mutual recursion are slower and very memory inefficient...if you have ever played around with recursion then you've no doubt gotten a stack overflow error if you use C/C++).

But of course many patterns are recursive in nature...sequences and series and other mathematical patterns (think fibonacci). And, if you learn it properly (at least in my opinion), it is sometimes much easier to think about problems recursively, and then convert into loops...

In any case, the key to using recursion effectively is to start with the base case(s). Once you have a place for the definition to terminate, then set up the recursive call (making the necessary preparations)...Think about it logically, trace the program steps and ensure that each recursive call is moving a little closer to the base case...and then have a little faith ;)

You could also learn Scheme for practice (with recursion)...unbounded data ftw...lol

EDIT: And I don't believe that recursive functions need to have parameters to be classified as recursive...I just think you didn't use the proper function prototype in your solution