Problem D
Melborp Lasrever A
Reversing a string (e.g., turning "foobar" into "raboof") is pretty straightforward. In fact, most programming languages include functions or methods that, given a string, will reverse it for you. However, in this problem, you must write the code to reverse the string yourself using a recursive algorithm.
Don’t worry, reversing strings recursively is very easy! Given a string $s$ with $n$ characters ($s_0s_1s_2\ldots s_{n-1}$), and a string concatenation operator ($+$), we can define a string reversal function $R$ like this:
\[ R(s) = \left\lbrace \begin{array}{l l} s_0 & \text {if }n=1 \\ R(s_1s_2\ldots s_{n-1}) + s_0 & \text {if }n > 1 \end{array}\right. \]When implementing your solution, you are only allowed to use the following string processing functions/methods in your programming language of choice:
-
String length
-
String concatenation
-
Extracting a substring (including individual characters) from a given string
If there are additional functions/methods you think you would need to use, please ask a proctor about it. However, if your language of choice includes a built-in mechanism to reverse strings, you must not use it.
Your solution must use a RECURSIVE function, using the definition presented above.
On the exam, any other type of solution will receive zero points!
EVEN IF KATTIS JUDGES IT AS CORRECT!
Input
The input contains a single string. The string contains only lowercase letters, no whitespace, and has a maximum length of 50 characters.
Output
You must output a single string, which will be the reversed value of the input.
| Sample Input 1 | Sample Output 1 |
|---|---|
melborp |
problem |
| Sample Input 2 | Sample Output 2 |
|---|---|
lasrever |
reversal |
