CODEWITHSUNDEEP
c++recursion
Nathan
Nathan

Reputation: 58

reverse array using recursion in c++

The assignment is relatively simple reverse the array in main using the ReverseStringRecursive function. However the limitation is I can only use a single int and a char nothing else that declares a variable (this includes the banning of for loops and so on). Additionally no extra libraries may be used I am limited to iostream and conio.h. The problem I'm having is that the string will be printed forward and then backwards when I just need it to be printed backwards. the reverseMe variable is pointing to a string in main that contains "abcdefghijklmnopqrstuvwxyz". This function is not suppose to print the string just reverse is then main will print the string.

// INCLUES AND NAMESPACES
#include <iostream>
#include<conio.h>
using namespace std;

// CONSTANTS
const int STRING_SIZE = 100;

// PROTOTYPES
int ReverseStringRecursive(char*);

// MAIN
int main() {
    // create a string
    char someString[STRING_SIZE] = "abcdefghijklmnopqrstuvwxyz";

    // display the string before being reversed
    cout << "The string contains: " << endl;
    cout << someString << endl << endl;

    // make the call to the recursive function
    cout << "CALL THE REVERSING FUNCTION" << endl << endl;
    ReverseStringRecursive(someString);

    // display the string after being reversed
    cout << "The string contains: " << endl;
    cout << someString << endl;

    // exit program
    _getch();
    return 0;
}
    int ReverseStringRecursive(char* reverseMe) {
// YOUR IMPLEMENTATION GOES HERE...
int position = 0;
char holder = ' ';

if (reverseMe[0] == '\0') {
    return 1;
}
else {
    holder = reverseMe[position];
}

ReverseStringRecursive(reverseMe + 1);

while (reverseMe[position] != '\0') {
    position++;
}
reverseMe[position] = holder;

return position;
}

Example output that I am getting:

"abcdefghijklmnopqrstuvwxyz zyxwvutsrqponmlkjihgfedcba"

what I'm suppose to get:

"zyxwvutsrqponmlkjihgfedcba"

Upvotes: 0

Views: 965

Answers (2)

Gardener
Gardener

Reputation: 2660

Tough problem. You have to shorten the inner string on each recursion by placing a '\0' on the last character before calling the recursive function and then performing the swap after the recursive call.

algorithm:

0. save the index of the last character in the string
1. Save the last character of the current string
2. Set the last character of the current string to null (use the saved index)
3. Call the recursive function starting one character in which will recurse the algorithm for the next inner string (we have already shortened the end of the recursed string)
4. Once the recursion has finished, set the last character to the first char of the current string; then
5. set the first character of the current string to the saved character (which was at the end)

This will work for odd-length strings as well.

The following code should work on a windows system. To make it work on Linux, simply comment out the conio.h include line, comment the __getch() line and uncomment the cin.getch() line.

// INCLUES AND NAMESPACES
#include <iostream>
#include <conio.h>

using namespace std;

// CONSTANTS
const int STRING_SIZE = 100;

// PROTOTYPES
int ReverseStringRecursive(char *);

char *orig;

// MAIN
int main()
{
  // create a string
  char someString[STRING_SIZE] = "abcdefghijklmnopqrstuvwxyz";

  orig = someString;

  // display the string before being reversed
  cout << "The string contains: " << endl;
  cout << someString << endl << endl;

  // make the call to the recursive function
  cout << "CALL THE REVERSING FUNCTION" << endl << endl;
  ReverseStringRecursive(someString);

  // display the string after being reversed
  cout << "The string contains: " << endl;
  cout << someString << endl;

  // exit program
  _getch();        // uncoment conio.h on a windows system
  //  std::cin.get();  // use this if on a linux system

  return 0;
}

int ReverseStringRecursive(char *reverseMe)
{
  int last_index = 0;
  while (reverseMe[last_index + 1] != '\0')
    last_index++;

  char save_char = reverseMe[last_index];

  if (*reverseMe != '\0') {
    reverseMe[last_index] = '\0';  // shorten the inner string by one

    // recurse on the shorter string
    ReverseStringRecursive(reverseMe + 1);

    // save the outer two characters
    reverseMe[last_index] = *reverseMe;
    *reverseMe = save_char;
  }
}

Upvotes: 2

MFisherKDX
MFisherKDX

Reputation: 2866

You are overwriting your terminating '\0' and therefore corrupting your string. When your while loop exists, reverseMe[position] is at '\0' and then you overwrite it with the value holder. Your string is no longer null-terminated and you are getting undefined behavior on your next while loop as it accesses outside the bounds of your array.

Upvotes: 0

Related Questions