C++ Recursive function has me stumped

Hey, I am having trouble implementing a c++ function that will allow the user to enter a lower and upper bounds and reverse everything in a char[] in between the bounds, so if array is,

char[] = {'A','B','C','D','E'};

and the user input was 1 and 4 for 1 as the lower bounds
and 4 being the upper bounds, then the output should be,

ADCBE

I know I am getting close with the code I have right now,
but I am not sure where my logic is incorrect...

---------------------------
the code I have for this function so far is,

Code:

---

void reOrder(char a1[], int start, int end){ // NOT WORKING
char temp;

if(start > end) {
cout << " " << endl;
for(int i = 0; i < 5; i++){
cout << a1[i] << " ";
}
cout << "" << endl;
return;
}
else{
temp = a1[end];
a1[end] = a1[start];
a1[start] = temp;
reOrder(a1, ++ start, -- end);

}
}

---

and my output is incorrect,

OUTPUT:
AEDCB

If anyone could help me figure this out I will greatly appreciate it, I am trying to learn recursion.

Quote:

---

Originally Posted by mrmodest

Hey, I am having trouble implementing a c++ function that will allow the user to enter a lower and upper bounds and reverse everything in a char[] in between the bounds, so if array is,

char[] = {'A','B','C','D','E'};

and the user input was 1 and 4 for 1 as the lower bounds
and 4 being the upper bounds, then the output should be,

ADCBE

...

and my output is incorrect,

OUTPUT:
AEDCB

If anyone could help me figure this out I will greatly appreciate it, I am trying to learn recursion.

---

Looks like you are simply misinterpreting the upper bound. That is, your output would be correct if the upper bound were 5 instead of 4.

But there isn't an index at 5. The assignment states:


a[0] = 'A' a[1] = 'B' a[2] = 'C'
a[3] = 'D' a[4] = 'E'

and the bounds are 1 and 4. Then after the function is run the array elements should

be:

a[0] = 'A' a[1] = 'D' a[2] = 'C'
a[3] = 'B' a[4] = 'e'

And what happens if you specify 3 as the upper bound?

If I use 1 and 3, where 3 is the upper bound, I get the correct output, but the assignment says 1 and 4 so something is wrong in my function... I suppose if I passed upper bounds -1 that works, but I am not sure if that would be allowed.

Usually, an off-by-one error like that indicates you have < when you need <=, or vice versa, or a similar issue with >. Take a careful look at every place you use those operators.

Quote:

---

Originally Posted by mrmodest

If I use 1 and 3, where 3 is the upper bound, I get the correct output, but the assignment says 1 and 4 so something is wrong in my function... I suppose if I passed upper bounds -1 that works, but I am not sure if that would be allowed.

---

Yes, you could change the input to the function call, but that doesn't seem to be the point of the exercise. Alternatively, you could change the way the function works.

Code isn't magic. The computer just does exactly what you tell it to do. And you can see what it's doing by stepping through your program with the debugger that comes with the compiler you are using. With a program like this you can even work out on paper what's going on. If you do that, I'm sure you'll spot the error within minutes.

Nothing to do with the recursion (D_Drmmr and Lindley have that in hand :)) but I would make a couple of points about your code:

1) You said you want to reverse part of the array, and that is indeed what your code is doing, but you have named your function reOrder, a much vaguer term. Anyone seeing a call to 'reOrder' will not know just how it is meant to reorder the array, without either looking at the code or reading documentation. Call it 'reverse' and everyone knows exactly what it is doing.

2) It is best for each function to do one thing only, i.e. in this case just reverse the array, but don't output it to cout as well. This means it would be usable in many more situations (i.e. ones where we don't want it to output the result to cout). So split out this part to a separate function:

Code:

---

void reverse(char a1[], const int start, const int end){ // NOT WORKING
    if(start > end) {
        return;
    } else {
        const char temp = a1[end];
        a1[end] = a1[start];
        a1[start] = temp;
        reverse(a1, ++start, --end);
    }
}

void outputArray(const char a1[], const int length)
{
    cout << " " << endl;
    for(int i = 0; i < length; i++){
        cout << a1[i] << " ";
    }
    cout << "" << endl;
}

---

Then call it after you call 'reverse'.

Quote:

---

Originally Posted by Peter_B

Code:

---

void reverse(char a1[], const int start, const int end){ // NOT WORKING
    if(start > end) {
        return;
    } else {
        const char temp = a1[end];
        a1[end] = a1[start];
        a1[start] = temp;
        reverse(a1, ++start, --end);
    }
}

---

---

Better to remove the almost-empty if statement....and let's make use of a standard algorithm while we're at it:

Code:

---

void reverse(char a1[], const int start, const int end)
{
    if(!(start > end))
    {
        std::swap(a1[end],a1[start]);
        reverse(a1, ++start, --end);
    }
}

---

Quote:

---

Originally Posted by Lindley

Better to remove the almost-empty if statement....and let's make use of a standard algorithm while we're at it:

---

Yes, it is. I didn't want to do all the OP's work for him though :)

I still haven't fixed the actual bug. Just manipulated the existing code a bit. Hopefully this helps to clarify where the problem is.

Quote:

---

Originally Posted by mrmodest

If I use 1 and 3, where 3 is the upper bound, I get the correct output, but the assignment says 1 and 4 so something is wrong in my function... I suppose if I passed upper bounds -1 that works, but I am not sure if that would be allowed.

---

The question is whether the upper bound is inclusive or not (whether the upper bound element takes part in the reversal). In the algorithm you have developed this is the case but according to specification this shouldn't be the case. You can fix this on two ways. You can write an adapter function which simply reduces the upper bound by one, like

Code:

---

void reOrderAdapter(char a1[], int start, int end) {
  void reOrder(a1, start,  end-1);
}

---

That's the simplest and most straightforward way. But you could also modify reOrder to accomplish the same by substituting end with end-1 at the termination criterion and the swap, like

Code:

---

  if(start > (end-1))

  // ...

  temp = a1[end-1];
  a1[end-1] = a1[start];
  a1[start] = temp;

---

Now the algorithm works as if end were reduced by one but at the cost of an error-prone modification and uglier code.

ABCDE
Bounds of 1 and 4 would be referring to
B to E
So, your output "AEDCB" is actually correct.
Note, A = 0, B = 1, C = 2, D = 3, E = 4.

Quote:

---

Originally Posted by Filthy_Utter

ABCDE
Bounds of 1 and 4 would be referring to
B to E

---

Only if you change the specification.

In this case the upper bound is defined not to be inclusive so bounds 1 and 4 are referring to B to D. See my previous reply.