reverse array using recursion in c++

Question

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"

Comments are not for extended discussion; this conversation has been moved to chat. — Cody Gray
– Cody Gray ♦, Commented Mar 7, 2019 at 0:04
There are two things that come to mind: Firstly, you could output the current state of the string at various points. Secondly, you could step through the code with a debugger. Both are skills worth learning, as they can be applied to other situations as well. Since you seem to be using an IDE (VS?), you should already have a debugger. Set a breakpoint anywhere in main(), switch your compile settings to "debug build" and hit the "start debugging" button. — Ulrich Eckhardt
– Ulrich Eckhardt, Commented Mar 7, 2019 at 6:30

Gardener · Accepted Answer · 2019-03-07 08:16:20Z

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;
  }
}

MFisherKDX · Accepted Answer · 2019-03-06 22:45:11Z

0

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.

answered Mar 6, 2019 at 22:45

MFisherKDX

2,8863 gold badges18 silver badges29 bronze badges

Collectives™ on Stack Overflow

reverse array using recursion in c++

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