Issue 5: Using Recursion on an Iterative Problem

Shoot for the moon. Even if you miss, you'll land among the stars.
- Les Brown  


As a part of our lab, we were given the exercise of making an recursive function for a standard iterative problem. Our goal was simple, produce the reversal of a string s, recursively. The challenge was the "recursively".

Anyone can do this problem with iteration; in fact, this is made even easier with python's ability to use more than just integers as the loop variable (a foreach loop really). 

def rev_string_iterative(s: str) -> str:
    """Return the reversal of string s, recursively.
    
    >>> rev_string_iterative("") == ""
    True
    >>> rev_string_iterative("H") == "H"
    True
    >>> rev_string_iterative("Hi") == "iH"
    True
    >>> rev_string_iterative("Hello!") == "!olleH"
    True
    """
    rev_string = ""
    for letter in s:
        rev_string = letter + rev_string
        
    return rev_string

However, should one attempt to solve this problem recursively, the very fact that there is an iteration solution that you're explicitly trying to avoid causes a great deal of conflict. This is because the recursive solution is awfully similar to the iterative solution. It is very easy to overlook a simple answer when you're trying to avoid anything similar to it.

We end up with something like this:

def rev_string_recursive(s: str) -> str:
    """Return the reversal of string s, recursively.
    
    >>> rev_string_recursive("") == ""
    True
    >>> rev_string_recursive("H") == "H"
    True
    >>> rev_string_recursive("Hi") == "iH"
    True
    >>> rev_string_recursive("Hello!") == "!olleH"
    True
    """
    if len(s) == 0:
        return s
    else:
        return s[-1] + rev_string_recursive(s[:-1]) 

In both cases, the goal was to take a single letter and append it to an accumulator. The only difference is, in the recursive example the function itself was the "loop". rev_string_recursive was called each time to with the whole string except the last letter, which was effectively identical the iterative task of moving the loop variable forward. In the iterative example, the loop was simply in a separate block of code.

If we trace the recursive function, we'll end up with something like this:
1. rev_string_recursive("") will return ""
2. rev_string_recursive("H") will return "H" + 1
3. rev_string_recursive("He") will return "e" + 2
4. rev_string_recursive("Hel") will return "l" + 3
and so on...

While this was just a practice, I didn't feel that it was necessarily a good practice. It feels as if we're reinventing the wheel - except we're doing it the hard way. There are a plethora of problems out there that require recursion to solve, many of which are contest worthy. It makes me wonder why we end up with exercises like this. Sure, those other problems may be hard, but even if we don't manage to solve all the problems we would still be able to gain a lot more practice from them.

Sorry, forgot to publish this!