Also relevant for recursion.

Reversing a String Iteratively and Recursively

A very common question regarding algorithms is reversing strings. Strings are one of the most basic data structures, and while developers spend a lot of their time manipulating strings, most basic functions are abstracted away. Why figure out the best way to reverse a string when you can just call .reverse? Because fundamentals are important (if annoying).

ITERATIVELY

Iteration is performing a process by looping over it continuously. For loops, while loops, and .each are examples of iteration. To reverse a string by iteration, we will loop over it, moving on letter at a time until the string is reversed. First, we’ll set up a while loop, keeping track of the number of iterations with the variable i:

This will run once for every character in the string.

However, we have to separate the string into an array of characters (Ruby does not play nice with trying to access and move characters from strings). This will then have to be reassembled into a string after the while loop:

Separating and reassembling the string.

In each iteration, we grab the last character in the array and add it to the front, while removing it from the end of the array:

And “Voila” becomes “alioV”.

And that’s it. After the loop is finished, the reversed string will be returned. But what if you (for whatever reason) hate iteration? If loops send you into a furious rage? What if you wanted a way to do this without ever entering a loop?

RECURSIVELY

Recursion is accomplishing method’s goal using the method itself, calling it within the method until a condition (called the “base case”) is reached. It essentially creates several “layers” of the function, going down as the method is called over and over, and returning information back on the way up.

As we go down the layers in our recursive string reversing algorithm, we’ll strip off characters, so our base case will be an empty string. We’ll set the function to not execute the meat of the code and return the empty string if it receives one as an argument:

The base case.

Now, if it’s not an empty string what do we do? We’ll call the function again without the first character, chopping the string down every layer shorter and shorter, and set a new string equal to whatever comes out of that stack:

What happens “on the way down”.

When receiving parts of the reversed string on the way back up, all each layer has to do is add the first character of the string it received to the end of the string coming from the level below it. When it reaches the top of the stack, the string will be reversed.

What happens “on the way up”.

For visualization, here’s what is occurring going down and coming back up:

                   "hello"         "olleh"
                     "ello"       "olle"
                       "llo"     "oll"
                         "lo"   "ol"
                           "o""o"
                             ""      

But remember: there’s always just .reverse.