-
I agree that this is a bad way to learn recursion, but here's a few ideas :
I think you'll have to pass a length into the sort function that's separate from the list length. That way you can turn the outer loop into a recursive call to your function, passing size - 1 each time.
If your homework requires that you use the exact prototypes given, you'll have to play games with only passing the unsorted beginning elements of the vector into each subsequent recursive call and then pushing back the sorted elements as you return from each recursive call.
As others have said, this isn't the most straightforward way of learning about recursion.
-
So, I've been tweaking some of my program, and I am getting stuck in an infinite loop and this is because I'm not decrementing my recursive function by one, I know this. However, when I am calling my remove function inside my sort function, shouldn't the size of the vector be decrementing by one each time?! I don't understand why I'm getting caught up in an infinite loop....can someone try to fix my code for me please!!!
Code:
int numbers::remove(int index)
{
if ((index >= 0) && ((index + 1) <= numbers.size()))
{
numbers.erase(numbers.begin() + index);
for (int i = 0; i < numbers.size(); i++)
cout << numbers[i] << " ";
}
else
{
cout << "Invalid index, element either below zero or has exceeded the size of the array";
exit(1);
}
}
vector <int> numbers::sort(vector <int> unsorted_list)
{
int i = 1;
if(unsorted_list.size() == 1)
{
cout << unsorted_list.at(0);
exit(1);
}
else
{
int temp;
for (int i = unsorted_list.size() - 1; i >= 0; i--) // Reading the dataset starts backwards.
{
for (int j = 0; j < unsorted_list.size() - 1; j++)
{
if (unsorted_list[j] > unsorted_list[j+1]) //Switching values to maximize convenience.
{
temp = unsorted_list[j];
unsorted_list[j] = unsorted_list[j+1];
unsorted_list[j+1] = temp;
}
}
}
numbers::remove(unsorted_list.size() - 1);
for (int k = unsorted_list.size() - 1; k >= 0; k--)
cout << unsorted_list[k] << " ";
numbers::sort(unsorted_list);
}
}
Thanks for all of the help!!! If you need more code to look at, let me know. Thanks again!
-
- Turn your compiler's warning level up to the max.
- Fix the fact that none of the control paths return a value, in either function!
- Why would a sort function EVER remove an item from the container!?!
- You're not even removing an item from the same container as the sort function, although surely that can't even compile because numbers is being used as both a variable AND a type!
- It's horridly ineficient to pass the vector by value (amoungst other things), and this function, if it worked, would be about O(n^4).
The only bit right with that code is the bubble sort (though the comments for it are all wrong), and you can't usefuly make bubble sort recursive.
Oh I guess the indentation is right too, I'll give you that.
Go back an learn about classes and functions again. The best thing you can do with that code is select it all and press the delete key.
Again, what algorithm do you plan on implementing recursively?
-
Read and understand the previous post first, especially the part about returning values from methods.
I still think it's a bad idea to code a bubble sort like this, but if you insist :
To translate to a recursive function, remove a loop from the iterative function and turn it into a recursive call instead. You've left the loop in and then added a recursive call on top of that.
To erase the last element, look at the pop_back() method. There's a corresponding push_back() to put something back on the end of the list.
Here's a basic outline
if list size is less than or equal to 1, return the list since a list that size is already sorted.
Go through the list in order, doing the inner loop of a normal bubble sort. This will push the biggest element to the end of the list.
Save the element at the end of the list (list.back()), then remove it from the list
call sort with this new shorter list
put the saved element back on the end of the list and return it.