C++ RSS C++ RSS

recursive function to use on linked list?

Please support our C++ advertiser: Intel Parallel Studio Home
Reply
1 2

•
•
Join Date: Apr 2008
Posts: 26
Reputation: dan_e6 is an unknown quantity at this point 
Solved Threads: 0
dan_e6 dan_e6 is offline Offline
Light Poster

recursive function to use on linked list?

 
0
  #1
May 20th, 2008
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.
Reply With Quote Quick reply to this message  
•
•
Join Date: Jan 2008
Posts: 3,819
Reputation: VernonDozier has a reputation beyond repute VernonDozier has a reputation beyond repute VernonDozier has a reputation beyond repute VernonDozier has a reputation beyond repute VernonDozier has a reputation beyond repute VernonDozier has a reputation beyond repute VernonDozier has a reputation beyond repute VernonDozier has a reputation beyond repute VernonDozier has a reputation beyond repute VernonDozier has a reputation beyond repute VernonDozier has a reputation beyond repute 
Solved Threads: 501
Featured Poster
VernonDozier VernonDozier is offline Offline
Senior Poster

Re: recursive function to use on linked list?

 
0
  #2
May 20th, 2008
•
•
•
•
Originally Posted by dan_e6 View 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.
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.
Reply With Quote Quick reply to this message  
•
•
Join Date: Apr 2006
Posts: 5,051
Reputation: John A is a splendid one to behold John A is a splendid one to behold John A is a splendid one to behold John A is a splendid one to behold John A is a splendid one to behold John A is a splendid one to behold John A is a splendid one to behold John A is a splendid one to behold 
Solved Threads: 332
Team Colleague
John A's Avatar
John A John A is offline Offline
Vampirical Lurker

Re: recursive function to use on linked list?

 
1
  #3
May 20th, 2008
>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.
"Technological progress is like an axe in the hands of a pathological criminal."

All my posts may be freely redistributed under the terms of the MIT license.
Reply With Quote Quick reply to this message  
•
•
Join Date: Apr 2008
Posts: 26
Reputation: dan_e6 is an unknown quantity at this point 
Solved Threads: 0
dan_e6 dan_e6 is offline Offline
Light Poster

Re: recursive function to use on linked list?

 
0
  #4
May 21st, 2008
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?
Reply With Quote Quick reply to this message  
•
•
Join Date: Apr 2008
Posts: 26
Reputation: dan_e6 is an unknown quantity at this point 
Solved Threads: 0
dan_e6 dan_e6 is offline Offline
Light Poster

Re: recursive function to use on linked list?

 
0
  #5
May 21st, 2008
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. }
Reply With Quote Quick reply to this message  
•
•
Join Date: Apr 2008
Posts: 26
Reputation: dan_e6 is an unknown quantity at this point 
Solved Threads: 0
dan_e6 dan_e6 is offline Offline
Light Poster

Re: recursive function to use on linked list?

 
0
  #6
May 21st, 2008
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.
Reply With Quote Quick reply to this message  
•
•
Join Date: May 2006
Posts: 248
Reputation: hammerhead is an unknown quantity at this point 
Solved Threads: 24
hammerhead's Avatar
hammerhead hammerhead is offline Offline
Posting Whiz in Training

Re: recursive function to use on linked list?

 
0
  #7
May 21st, 2008
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
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.
There are 10 types of people in the world, those who understand binary and those who don't.

All generalizations are wrong. Even this one.
Reply With Quote Quick reply to this message  
•
•
Join Date: Apr 2008
Posts: 26
Reputation: dan_e6 is an unknown quantity at this point 
Solved Threads: 0
dan_e6 dan_e6 is offline Offline
Light Poster

Re: recursive function to use on linked list?

 
0
  #8
May 21st, 2008
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.
Reply With Quote Quick reply to this message  
•
•
Join Date: May 2006
Posts: 248
Reputation: hammerhead is an unknown quantity at this point 
Solved Threads: 24
hammerhead's Avatar
hammerhead hammerhead is offline Offline
Posting Whiz in Training

Re: recursive function to use on linked list?

 
0
  #9
May 21st, 2008
>>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.
There are 10 types of people in the world, those who understand binary and those who don't.

All generalizations are wrong. Even this one.
Reply With Quote Quick reply to this message  
•
•
Join Date: Apr 2008
Posts: 26
Reputation: dan_e6 is an unknown quantity at this point 
Solved Threads: 0
dan_e6 dan_e6 is offline Offline
Light Poster

Re: recursive function to use on linked list?

 
0
  #10
May 21st, 2008
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.
Reply With Quote Quick reply to this message  
Reply
1 2

Quick Reply to Thread
This thread is more than three months old.
Perhaps start a new thread instead?
•
•
•
•
•
•
•
•
Message:
•
•
•
•



Similar Threads
Other Threads in the C++ Forum
Thread Tools Search this Thread



api array arrays based binary c++ c/c++ calculator char char* class classes code coding compile console conversion convert count database delete deploy desktop developer directshow dll download dynamic dynamiccharacterarray email encryption error file forms fstream function functions game generator givemetehcodez google graph gui homeworkhelp iamthwee ifstream input int java lib linkedlist linker list loop looping loops map math matrix memory multiple news number numbertoword output pointer problem program programming project python random read recursion recursive reference return rpg sorting string strings temperature template templates test text text-file tree unix url variable vector video visual visualstudio win32 windows winsock wordfrequency wxwidgets
About Us | Contact Us | Advertise | DaniWeb | Acceptable Use Policy | RSS Feed

©2003 - 2009 DaniWeb® LLC