c++ recursive function, can't figure out whats wrong?

Question

I can't figure out whats wrong with my function. It doesn't do anything, here is the prompt and my function

Write a recursive function that has as arguments an array of characters and two bounds on array indices. The function should reverse the order of those entries in the array whose indices are between the two bounds. For example, suppose that the array is:


a[5] = "abcde";


and the bounds are 1 and 3. Then after the function is run the array elements should be:


"adcbe".



char *reorder(char ptr[], int b1, int b2)
{
if( b2-b1 <= 1)
{
cout << "\n\nEnd Reached\n\n";
return ptr;
}

char swap;
swap = ptr[b1];
cout << ptr[b1];
ptr[b1] = ptr[b2];
cout << ptr[b1];
ptr[b2] = swap;
return reorder(ptr,b1++,b2--);
}

I get the error Unhandled exception at 0x00411ad9 in Lab9.exe: 0xC00000FD: Stack overflow. and it points to the beginning bracket of the function

Answer 1

I'm not sure if this is correct but here's what I suggest



instead of:



return reorder(ptr, b1++, b2--);



try:



return reorder(ptr,++b1, --b2);



from what i understand, is that it will do the subtraction first before sending it back into your recursive structure



the error you're getting is that your base case isn't being met as in b2-b1 is never less than or equal to 1.



i'm not sure it will work but it would in java.

Answer 2

Hm....



















It is looks like string reverse function.



U r algorithm is can be dangerous with stack.

The handle of recusv b2-b1 <= 1 is bad idea.

And using pre-inc/dec is more bad idea.

As u know, pre-inc/dec is inc/dec after execution, not before execution.

return reorder(ptr, b1++, b2--)

shld be:

return reorder(ptr, b1+1, b2-1)

or

return reorder(ptr, ++b1, --b2)



Look the proccess:

pos/val

0 1 2 3

a b c d



swap proc: b2-b1 (<= 1)

swap 0 <-> 3; 3 (f)

swap 1 <-> 2; 1 (t)// terminate recrsv



recursv just :

reorder(ptr, 0, 3)

and pos 1 & 2 is never swap.

And result will be: dbca



but if

pos/val

0 1 2 3 4

a b c d e



swap proc: b2-b1 (<= 1)

swap 0 <-> 4; 4 (f)

swap 1 <-> 3; 2 (f)

swap 2 <-> 2; 0 (t)// terminate recrsv



It is valid reorder

result will be edcba



Fix:

char *reorder(char ptr[], int b1, int b2)

{

if( b2<=b1)

{

cout << "\n\nEnd Reached\n\n";

return ptr;

}

char swap;

swap = ptr[b1];

cout << ptr[b1];

ptr[b1] = ptr[b2];

cout << ptr[b1];

ptr[b2] = swap;

return reorder(ptr,b1+1,b2-1);

}

Answer 3

Ichigo is right. b1 and b2 never change values, you can't get out of your recursion. ++b1 and --b2 are the parameters you have to pass from within reorder to reorder!

Answer 4

Stack overflows are probably the most common bug when developing recursive functions. What they mean is that the mechanism for "unwinding" the recursion didn't trip before the stack (used on all function calls) ran out of room.



Essentially, your recursion-ending condition wasn't met.



Hope that helps.

Answer 5

Stack overflow means it's calling itself over and over until it runs out of memory. What arguments are you calling it with?

Answer 6

I wrote a program similar to yours. My function reverses a string, but it can also do the same thing yours can. The function depends on whether the string has an even length or odd length, so I had to create two cases to adjust.



#include

#include

using namespace std;



string reverse(string str, int start, int end);



int main()

{

string a, b;

cout << "Enter some text, and I will reverse it for you.\n";

getline(cin,a);

b = reverse(a,0,a.length()-1);

cout << "In reverse, the text is: " << b << ".\n\nPress enter to exit.\n";

cin.get();

return 0;

}



string reverse(string str, int start, int end)

{

if ((start+end)%2==0)

{

if (start!=end)

{

char temp;

temp = str[start];

str[start] = str[end];

str[end] = temp;

return (reverse(str,start+1,end-1));

}

else

return str;

}

else

{

if (start!=end+1 || end!=start-1)

{

char temp;

temp = str[start];

str[start] = str[end];

str[end] = temp;

return (reverse(str,start+1,end-1));

}

else

return str;

}

}