| | |
recursive function to use on linked list?
Please support our C++ advertiser: Intel Parallel Studio Home
![]() |
•
•
Join Date: Jan 2008
Posts: 3,819
Reputation:
Solved Threads: 501
•
•
•
•
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.
C++ Syntax (Toggle Plain Text)
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.
>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.
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.
All my posts may be freely redistributed under the terms of the MIT license.
•
•
Join Date: Apr 2008
Posts: 26
Reputation:
Solved Threads: 0
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?
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?
•
•
Join Date: Apr 2008
Posts: 26
Reputation:
Solved Threads: 0
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
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)
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(); } } }
•
•
Join Date: Apr 2008
Posts: 26
Reputation:
Solved Threads: 0
okay i fixed it and it works fine now.....
the problem was in the
i needed to set current to start_ptr NOT re-declare it everytime!!!! now it works fine.
the problem was in the
C++ Syntax (Toggle Plain Text)
if (current == NULL )
i needed to set current to start_ptr NOT re-declare it everytime!!!! now it works fine.
I dont think your code classifies as recursion. Neither does it satisfy the question
This is what I would do to check if a link list is sorted using recursion
Note that there are two base cases.
•
•
•
•
bool isSorted(nodeType *L)
C++ Syntax (Toggle Plain Text)
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.
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.
All generalizations are wrong. Even this one.
>>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.
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.
All generalizations are wrong. Even this one.
![]() |
Similar Threads
- Recursive procedure (to display a linked list) (Pascal and Delphi)
- Algorithms (C++)
- Issues storing singlylinked lists in a singlylinked list. (C++)
- Recursive Insertion on Linked Lists (C++)
- Sorting in Python (Python)
Other Threads in the C++ Forum
- Previous Thread: strtoking...
- Next Thread: Comparison Counting using C++
| 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






