•
•
•
•
What is DaniWeb IT Discussion Community?
You're currently browsing the C++ section within the Software Development category of DaniWeb, a massive community of 428,386 software developers, web developers, Internet marketers, and tech gurus who are all enthusiastic about making contacts, networking, and learning from each other. In fact, there are 3,588 IT professionals currently interacting right now! Registration is free, only takes a minute and lets you enjoy all of the interactive features of the site.
Please support our C++ advertiser: Programming Forums
Views: 408 | Replies: 10
 |
•
•
Join Date: Apr 2008
Posts: 26
Reputation: 
Rep Power: 1
Solved Threads: 0
Light Poster
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.
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.
•
•
Join Date: Jan 2008
Posts: 1,780
Reputation:
Rep Power: 8
Solved Threads: 219
•
•
•
•
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:
cplusplus Syntax (Toggle Plain Text)
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.
•
•
Join Date: Apr 2006
Location: Canada
Posts: 4,505
Reputation: 
Rep Power: 17
Solved Threads: 277
>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.
tuxation.com - Linux articles, tutorials, and discussions
•
•
Join Date: Apr 2008
Posts: 26
Reputation:
Rep Power: 1
Solved Threads: 0
Light Poster
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:
Rep Power: 1
Solved Threads: 0
Light Poster
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
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:
Rep Power: 1
Solved Threads: 0
Light Poster
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
if (current == NULL )
i needed to set current to start_ptr NOT re-declare it everytime!!!! now it works fine.
•
•
Join Date: May 2006
Location: India
Posts: 247
Reputation:
Rep Power: 3
Solved Threads: 24
Posting Whiz in Training
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)
This is what I would do to check if a link list is sorted using recursion
C++ Syntax (Toggle Plain Text)
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.
•
•
Join Date: Apr 2008
Posts: 26
Reputation:
Rep Power: 1
Solved Threads: 0
Light Poster
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.
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.
•
•
Join Date: May 2006
Location: India
Posts: 247
Reputation:
Rep Power: 3
Solved Threads: 24
Posting Whiz in Training
>>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 7: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.
•
•
Join Date: Apr 2008
Posts: 26
Reputation:
Rep Power: 1
Solved Threads: 0
Light Poster
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.
"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.
|
•
•
•
•
•
•
•
•
DaniWeb C++ Marketplace
•
•
•
•
Currently Active Users Viewing This Thread: 1 (0 members and 1 guests)
Linear Mode
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++
