As mentioned earlier, any problem that can be solved with iteration can also be solved with recursion. If you are having trouble seeing a recursive approach to a problem, it can sometimes help to translate an iterative solution. Although this may not always produce the simplest or cleanest recursive algorithm, it can be a useful alternative way to reach a recursive design.
Let us consider a function to clean up extra spaces in a string. We want to take something like "This is a string with extra spaces." and turn any run of multiple spaces into a single space, so that it becomes "This is a string with extra spaces.".
One possible algorithm is shown below. It loops through the string one character at a time. inSpace tracks whether or not we are currently in a sequence of spaces. If a character is a space, and we are not already in a sequence of spaces, we add it to the result and then mark that we are in a space sequence. Any more spaces we see right after that will get ignored. When we see a non-space, we add it to the result and mark that we are not in a space sequence. That way, we know that the next space we see will start a new run of spaces:
Now, let us translate this into a recursive solution. First, we need to identify the base case. What stops the loop? That should also stop the recursion. In this case, the loop stops if there are no more characters in input. That sounds like a base case:
Now for the recursive case. The loop starts with the first character, then goes to the second, etc... Each iteration only worries about the “next” character. To make that recursive, we have two choices:
We can pass the index of the character we are looking at as a parameter.
We will use the second option, as it is simpler to implement. It is not as efficient, but after building the simple version, we could always go back and refine it later.
So our solution will need to separate the first character from the rest of the string. We will call that first character firstChar and the other characters rest. Each function call will only be responsible for making a decision about the firstChar and then making a recursive call with rest. For now we won’t worry about spaces, we will include every single character to verify that we are working our way through the string:
The iterative version has a variable that exists throughout the entire loop: inSpace. In recursion, the only way to store a value across all the entire process is to make it a parameter. So will modify the cleanUpSpaces function to include a boolean parameter inSpace that tracks whether we are currently in a sequence of spaces. That can be used to decide whether to include or skip the firstChar in the result:
Notice that line 31 has some debugging information. Try uncommenting that line and running the program to better see the step by step progression of the algorithm. Note that the actual output is being built up as return from each function call. So the debugging output will appear to build from the end of the string (where the recursion ended) back to the start of the string (where it began).
Build the code that would get us started on a version of the algorithm that would use an index to track our position in the string instead of making successively shorter substrings. (Ignore the | symbols, they are a formatting convenience).
