Recursive function troubles

[ChiefMAHAN]

Good afternoon,

I was recently assigned a project that implements a recursive function in order to reverse the contents of a vector.

Here are the instructions:
// Write a recursive function reverse that takes a vector of integers (by reference) and a starting and ending position in the vector. It then
reverses the contents of the vector (contents in opposite order) from start to end. The idea behind a recursive solution is that to reverse an entire vector you swap the values at the start and end, then you reverse the remaining inner part of the vector.

Note, you wll always pass the same vector to the recursive call, but you will manipulate start and end to represent the sucessfully smaller inner vector. start and end will also be used to form the base case. The following checks the behavior of reverse and provides examples:

std::vector<int> empty, empty_expected;
reverse(empty, 0, -1);
assert(empty == empty_expected);

std::vector<int> one{ 1 }, one_expected{ 1 };
reverse(one, 0, 0);
assert(one == one_expected);

std::vector<int> two{ 1, 2 }, two_expected{ 2, 1 };
reverse(two, 0, 1);
assert(two == two_expected);

std::vector<int> odd{ 1, 2, 3, 4, 5, 6, 7 }, odd_expected{ 7, 6, 5, 4, 3, 2, 1 };
reverse(odd, 0, odd.size() - 1);
assert(odd == odd_expected);

std::vector<int> even{ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 }, even_expected{ 10, 9, 8, 7, 6, 5, 4, 3, 2, 1 };
reverse(even, 0, even.size() - 1);
assert(even == even_expected);

Heres the function I currently have (I understand this might not even be close, but I guess that shows you just how lost I am):

[code]int reverse(std::vector<int> &, int start, int end) {
    while (odd.size() >= 0) {
        for (int i = odd.size() - 1; i >= 0; i--) {
            std::vector<int> = odd[i];
        }
   }
     return 0;
}

I'm especially thrown off by the part in the instructions that says, "Note, you will always pass the same vector to the recursive call...". However, in the examples shown with asserts, it appears a different vector is always passed to the recursive call.

Thank you in advanced for your time and input.

[dutch]

Use code tags.

[markyrocks]

this was way harder than it needed to be. I must be tired... I wasn't able to get assert() on my setup so i just kinda made my own comparison.

#include <Windows.h>
#include <iostream>
#include <vector>

using namespace std;

void reverse(std::vector<int> &e ,int start, int end) {
	std::vector<int> copy;

	for (int i = end - 1; i > 0; i--) {
		copy.push_back(e[i]);
	}
	e.swap(copy);
}

bool assert1(std::vector<int> a, std::vector<int> b) {
	for (int i = 0; i < a.size(); i++) {
		if (!(a[i] == b[i])) {
			return false;
		}

	}
	return true;

}

int main() {
std::vector<int> even{ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 }, even_expected{ 10, 9, 8, 7, 6, 5, 4, 3, 2, 1 };

reverse(even, 0, even.size());

if (assert1(even, even_expected)) {
	cout << " Vectors Even";
}
else { cout << "Vectors Uneven"; }

}

[Duthomhas]

Neither of you have written a recursive function.

In order for a function to be recursive, it must call itself. Ideally it should also know when to stop calling itself.

For example:

#include <iostream>

void print_n_to_m( int n, int m )
{
  if (n <= m)
  {
    std::cout << n << "\n";
    print_n_to_m( n + 1, m );
  }
}

int main()
{
  print_n_to_m( 1, 10 );
}

I could have just written a loop:

  for (int n = 1; n <= 10; n++)
    std::cout << n << "\n";

See how they recursive function and the loop are similar?


You are being asked to do the same kind of thing to reverse your vectors. For example, given the vector { 1, 2, 3, 4, 5 }, it would get reversed by exchanging the first and last elements, then the next two, and so on until the indices meet or cross.

    1 2 3 4 5

    5 2 3 4 1
    ↑       ↑

    5 4 3 2 1
      ↑   ↑

    5 4 3 2 1
        ⇈

In the function itself there is never any need to check the vector’s .size(). All the information you need is given by the arguments: a reference to the vector, the current ‘start’ element, and the current ‘end’ element. The function can safely assume that both start and end are < .size().

ChiefMAHAN wrote:

I'm especially thrown off by the part in the instructions that says, "Note, you will always pass the same vector to the recursive call...". However, in the examples shown with asserts, it appears a different vector is always passed to the recursive call.

There are two different contexts here.

In the function, you will call the function again (recursively) using the same vector argument given to it. This is reasonable, since the function should only be interested in modifying the currently-being-modified vector.

void reverse( std::vector<int> & xs, int start, int end )
{
  if (...)
    reverse( xs, ... );  // call this function again to continue reversing the same vector given to it 
}

However, the user of the function (in your case, the main() function) can call the reverse() function as many times as it wants with any vector it likes. (This is kind of the whole point of a function.) This kind of call is not recursive.

The asserts are testing your function for correctness on an important boundary issue:

  • Does it work properly for vectors with an even number of elements?
  • Does it also work properly for vectors with an odd number of elements?


@markyrocks
The assert() macro is used to validate preconditions and postconditions in code, and in the case of the OP’s homework, to test and validate that the function works correctly. In order to use it you must #include <cassert> (or <assert.h>).

Don’t #include <windows.h> if you don’t need it.

Hope this helps.

[Manga]

I don't think this example meets the requirements as I don't pass a start and end position to the function... But it is simple and it gives the desired results.

#include <iostream>
#include <vector>

using namespace std;

void show(vector<int> v) {
	for (size_t i = 0; i < v.size(); i++) {
		cout << v[i] << " ";
	}
}

void reverse(vector<int>& v, int i) {
	if (v.size()/2 > i) {
		int temp = v[i];
		v[i] = v[v.size() - 1 - i];
		v[v.size() - 1 - i] = temp;
		reverse(v, ++i); //recursive call
	}

}



int main() {
	vector<int> even{ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 }, odd{ 1, 2, 3 };

	reverse(even, 0);
	show(even);
	cout << endl;
	reverse(odd, 0);
	show(odd);


	return 0;
}

[Duthomhas]

@Manga
As it does not meet the assignment’s requirements, if you were to turn that in you would fail the assignment. Why suggest it then?

[Manga]

Ok Duthomhas... after some minor tweeking to the code I come up with this...

#include <iostream>
#include <vector>

using namespace std;

void show(vector<int> v) {
	for (size_t i = 0; i < v.size(); i++) {
		cout << v[i] << " ";
	}
}


void reverse(vector<int>& v, int start, int stop) {
	if (v.size()/2 > start) {
		int temp = v[start];
		v[start] = v[v.size() - 1 - start];
		v[v.size() - 1 - start] = temp;
		reverse(v, ++start, stop - start); //recursive call
	}

}


int main() {
	vector<int> even{ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 }, odd{ 1, 2, 3 };

	reverse(even, 0, even.size()-1);
	show(even);
	cout << endl;
	reverse(odd, 0, even.size()-1);
	show(odd);


	return 0;
}

That should pass.

[Duthomhas]

If I were grading it I would take points off for using .size() and your index handling.

Think harder. Both start and stop are direct indices into the array vector. You do not need .size().

You are very close.

Hint: how do you know when you are done if all you have to examine are start and stop?

[ChiefMAHAN]

Thank you so much for all the replies, you guys are the best! I got it all figured out with all your help... sounds like some of you guys had just as much fun with this as I did haha, thanks again.

[markyrocks]

sry missed the recursive part

void reverse(std::vector<int>& e, int start, int end) {
	
	if (start != end && start < end) {
	int temp = e[start];
	e[start] = e[end-1];
	e[end - 1] = temp;
	reverse(e, start + 1, end - 1);

	}
	
}

[Duthomhas]

Why was markyrocks reported?

[dutch]

Why was markyrocks reported?

Oooooo, he's in trouble now!!!

(@markyrocks, just ignore it. It's meaningless.)

[markyrocks]

apparently that function i wrote was so hard core that someone thought it was a troll post