943,708 Members | Top Members by Rank

Software Development > C++ > recursive function to use on linked list?
Ad:
  • C++ Discussion Thread
  • Unsolved
  • Views: 2697
  • C++ RSS
You are currently viewing page 1 of this multi-page discussion thread
Permalink
May 20th, 2008
0

recursive function to use on linked list?

Expand Post »
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.
Similar Threads
Reputation Points: 10
Solved Threads: 0
Light Poster
dan_e6 is offline Offline
26 posts
since Apr 2008
Permalink
May 20th, 2008
0

Re: recursive function to use on linked list?

Click to Expand / Collapse  Quote originally posted by 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.
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:

C++ Syntax (Toggle Plain Text)
  1. while (L != NULL)
  2. {
  3.      if (some condition)
  4.      {
  5.           // return true or false
  6.      }
  7.      L = L->next;
  8. }
  9.  
  10. // 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.
Featured Poster
Reputation Points: 2614
Solved Threads: 687
Posting Expert
VernonDozier is offline Offline
5,372 posts
since Jan 2008
Permalink
May 20th, 2008
1

Re: recursive function to use on linked list?

>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.
Team Colleague
Reputation Points: 2240
Solved Threads: 338
Vampirical Lurker
John A is offline Offline
5,055 posts
since Apr 2006
Permalink
May 21st, 2008
0

Re: recursive function to use on linked list?

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?
Reputation Points: 10
Solved Threads: 0
Light Poster
dan_e6 is offline Offline
26 posts
since Apr 2008
Permalink
May 21st, 2008
0

Re: recursive function to use on linked list?

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

C++ Syntax (Toggle Plain Text)
  1.  
  2. void Library::sorted()
  3. {
  4.  
  5.      if (current==NULL)
  6.      {
  7.         node *current = start_ptr;
  8.      }
  9.  
  10.      if (! (current->next == NULL))
  11.      {
  12.         node *t = current->next;
  13.         if (current->pdata->nAuthors > t->pdata->nAuthors)     
  14.            {
  15.                           cout << "List is not in order." << endl;
  16.            }
  17.            else
  18.            {
  19.                current = current->next;
  20.                sorted();
  21.            }           
  22.  
  23.      }
  24. }
Reputation Points: 10
Solved Threads: 0
Light Poster
dan_e6 is offline Offline
26 posts
since Apr 2008
Permalink
May 21st, 2008
0

Re: recursive function to use on linked list?

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

the problem was in the

C++ Syntax (Toggle Plain Text)
  1. if (current == NULL )

i needed to set current to start_ptr NOT re-declare it everytime!!!! now it works fine.
Reputation Points: 10
Solved Threads: 0
Light Poster
dan_e6 is offline Offline
26 posts
since Apr 2008
Permalink
May 21st, 2008
0

Re: recursive function to use on linked list?

I dont think your code classifies as recursion. Neither does it satisfy the question
Quote ...
bool isSorted(nodeType *L)
This is what I would do to check if a link list is sorted using recursion
C++ Syntax (Toggle Plain Text)
  1. bool sorted(node *curr)
  2. {
  3.      if(curr->next==NULL)
  4.      {
  5.                    return true;
  6.      }
  7.      else if(curr->val>curr->next->val)
  8.      {
  9.           return false;
  10.           }
  11.  
  12.           else
  13.           {
  14.               return sorted(curr->next);
  15.            }
  16. }

Note that there are two base cases.
Reputation Points: 46
Solved Threads: 24
Posting Whiz in Training
hammerhead is offline Offline
248 posts
since May 2006
Permalink
May 21st, 2008
0

Re: recursive function to use on linked list?

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.
Reputation Points: 10
Solved Threads: 0
Light Poster
dan_e6 is offline Offline
26 posts
since Apr 2008
Permalink
May 21st, 2008
0

Re: recursive function to use on linked list?

>>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.
Last edited by hammerhead; May 21st, 2008 at 8:29 am.
Reputation Points: 46
Solved Threads: 24
Posting Whiz in Training
hammerhead is offline Offline
248 posts
since May 2006
Permalink
May 21st, 2008
0

Re: recursive function to use on linked list?

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.
Reputation Points: 10
Solved Threads: 0
Light Poster
dan_e6 is offline Offline
26 posts
since Apr 2008

This thread is more than three months old

No one has posted to this discussion for at least three months. Please let old threads die and do not reply to them unless you feel you have something new and valuable to contribute that absolutely must be added to make the discussion complete. Otherwise, please start a new thread in this forum instead.
Message:
Previous Thread in C++ Forum Timeline: strtoking...
Next Thread in C++ Forum Timeline: Comparison Counting using C++





About Us | Contact Us | Advertise | Acceptable Use Policy
Forum Index | Build Custom RSS Feed


Follow us on Twitter


© 2011 DaniWeb® LLC