Program blowing up after using recursion

Question

Modifying my reverse a string function to add recursion. Unfortunately, my program keeps blowing up.

Stepped through my code in Visual Studio and for some reason the watch window will say i is equal to the length of the string (i.e. the terminating condition to exit the while loop). I step over it one last time and it says i is now one less than the string length. Then it stays in the while loop forever.

I know this sounds confusing, so I will give an example. I enter "Spongebob" and it does everything I want it to (i.e. says the length of Spongebob is 9, prints "bobegnopS", increments i to the string length, etc), but then it says i is now 8 (i.e. it was just at 9) and never exits the while loop.

Here is my ReverseString() function:

void ReverseString(char * string, bool stringReversed, int stringLength, int i)
{
    i++;
    if(!stringReversed)
    {
        while(*string != '\0')
        string++;
    }
    stringReversed = true;

    while(i < stringLength)
    {
        string--;
        std::cout << *string;
        ReverseString(string, stringReversed, stringLength, i);
    }
   }

Here is the call:

    case 3:
    //Learn By Doing 16.6
    {
        char string[BUFFER_LENGTH];
        bool stringReversed = false;

        int base = 0;
        int exponent = 0;

        std::cout << "\nEnter base: " << std::endl;
        std::cin >> base;

        std::cout << "\nEnter exponent: " << std::endl;
        std::cin >> exponent;

        //Print pow
        NewLine();
        std::cout << base << " to the " << exponent << " is " << pow(base, exponent);

        //Reverse string using recursion
        std::cout << "\nEnter string: " << std::endl;
        std::cin >> string;


        NewLine();
        int stringLength = strlen(string);
        int i = 0;
        ReverseString(string, stringReversed, stringLength, i);

    }

You mean I cannot have ReverseString be void since it is a recursive function?? So I should make it char * ReverseString making it return a character pointer?? — MrPickle5
– MrPickle5, Commented Feb 23, 2013 at 3:59

Slava · Accepted Answer · 2013-02-23 04:58:35Z

3

When you write a recursive function you always need to specify condition when to stop. Imagine you want to write naive factorial recursive implementation. So idea is to calculate it like this:

n! = n * (n-1) *...*2*1

If you look into sequence you can see that you need to stop at value 1. So naive recursive implementation could be this:

int factorial( int n )
{
   // stop when we reached 1
   // otherwise we never finish
   if( n == 1 ) return 1; 
   // now do the magic
   return n * factorial( n - 1 );
}

The fact that you need to return a value or not does not change the fact that you need to put a stop condition, otherwise your recursive function will never stop.

answered Feb 23, 2013 at 4:58

Slava

44.4k2 gold badges54 silver badges100 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

Beta · Accepted Answer · 2013-02-23 04:53:12Z

1

void ReverseString(char * string, bool stringReversed, int stringLength, int i)
{
  ...
  while(i < stringLength)
  {
    string--;
    std::cout << *string;
    ReverseString(string, stringReversed, stringLength, i);
  }
}

Nothing inside the loop modifies i or stringLength (the function ReverseString takes them by value, not by reference.) So it can never terminate.

answered Feb 23, 2013 at 4:53

Beta

99.5k18 gold badges159 silver badges156 bronze badges

Collectives™ on Stack Overflow

Program blowing up after using recursion

2 Answers 2

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related