Overview

In this assignment, the student will write a C$++$ program that implements a

recursive algorithm to reverse a character string.

When completing this assignment, the student should demonstrate mastery of

the following concepts:

$$ Non$-$Tail Recursion

$$ Programming Restraints

$$ Advanced Call Stack Usage

Assignment

Write a C$++$ program with a recursive function that reverses a character

string. Consider the following starting code:

$//$ INCLUES AND NAMESPACES

#include

using namespace std;

$//$ DEFINES

#define 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

return $0$;

$\}$

You are to provide an implementation for $$ReverseStringRecursive$()$ that will

physically reverse the letters in the provided input string. Your solution

should scale to accommodate any properly terminated character string with

sufficient memory allocated.

When writing your solution, you must operate under an extreme restriction!

Aside from the single character pointer being provided as an argument to the

function as specified in the prototype, you may only declare a single $$char$$

and a single $$int$$ variable at the beginning of your function$$s body. After

that point, you may not declare any more variables in your function.

Additionally, you will not be able to use other libraries to assist you since

those libraries have functions that would naturally declare additional

internal variables. For examples, if you decide that you would like to

$$#include $$ in order to take advantage of the $$strlen$()$ function

in your algorithm, this would invalidate your solution; you must stick to

simple conditions and loops all the way through the recursive function

definition.

To solve this problem with the provided restrictions, you will have to make

use of non$-$tail recursion and consider how to use the call stack in a clever

way to manage an arbitrarily large string to reverse while adhering to the

previously mentioned variable declaration restriction.

NOTE: This restriction includes the use of external library calls as these

calls implicitly declares additional variables. It$$s still a violation; you

may only declare one additional $$int$$ and one additional $$char$.$Please take note that displaying the string in reverse order alone is not a sufficient solution to this

problem. The string must be physically reversed so the second display call in the driver shows it in

reverse order in the output.