I am trying to get better at recursion!

I spent a couple of hours studying recursion, as it seems to be a weak point for me right now. In order to this, I went back to the week 4 recursion lab and re-worked through the problems. Also, I went back to some of the class examples.

I believe one of the problems I have is that I over-think the problems. For example, I was working on the problem of trying to reverse a string. My first attempt at a recursive solution was to create an accumulator that would hold the last letter of the string. Then, if the string was one character long, I would return only that letter. If the string was longer, I would re-call the function using the current string, minus the last letter. The code looked like:


def rev_string(s: 'str') -> str:

    new = ""
    if len(s) == 1:
        return s
    else:
        return rev_string(s[:-1])


This is clearly wrong because obviously my accumulator variable does nothing. I end up returning the last letter of the string s, because I am not actually adding on letters to my accumulated string, new.

After some thought, I realize that the function I was trying to write practically writes itself. For example, if I want to reverse a string, I simply take the last letter and add the reversal of all preceding letters:


def rev_string(s: 'str') -> str:
 
    return s[-1] + rev_string(s[:-1]) if len(s) > 0 else s


Not only does this function work, it looks a lot simpler.
Brief explanation on how it works:
If the string, s, is longer than a single character, take the last letter of s and add the reversed string of all preceding letters (by calling the function recursively).
If the string, s, is only a single character, simply return s. (This is the 'base case')

For example, if I want to reverse 'asdf', I want to take the last letter 'f' and add rev_string('asd').
But rev_string('asd') gives 'd' + rev_string('as'), and so on. So, the final return value ends up being
'fdsa', as desired.

This was sort of a long post on a seemingly easy example, but recursion was something that did not come naturally to me.