I had an exercise and tried to use parts of code I found here on another person's question, but I found that I needed a part of code that I have no idea why I do.
The full code I was using for my function is this:
def rreverse(s): if s == "": return s else: return rreverse(s[1:]) + s
But I only used the else as a statement, and I didn't get the result I was hoping for.
def recur_reverse(x): if x != "": return recur_reverse(x[1:]) + x
I got TypeError saying "unsupported operand type(s) for +: 'NoneType' and 'str'."
What is the logic behind this first example working fine and the second one throwing an error when the difference is this if statement? and why is my version incorrect?
In the recursion, you each time "pop" the first element
s from the string
s, and you append it to the reverse of the remaining elements
But this means that we will eventually make a call with an empty string (since a string has a fixed, length, and if we each time pop off a character, eventually we will run out of characters).
An empty string has no first character
s, so this will raise an
IndexError, to prevent that we implement as base case the empty string: the reverse of an empty string is an empty string. So:
def rreverse(s): if s == "": # empty string (base case) return s else: # non-empty string (recursive case) return rreverse(s[1:]) + s
If you do not implement this case, then there is a codepath with no explicit return expression. If a function does not return something explicitly, Python will return
But note that we make
rreverse(s[1:]) calls, if that returns in
None, we will thus add
None and a string (for example
'a') together. But that makes no sense: Python does not know how to add a
None and a string (well it makes no sense to do that), hence the error.
Your version thus will for example for
rreverse('ab') make calls like (not valid Python, only to demonstrate the problem):
# second version rreverse('ab') -> rreverse('b') + 'a' -> rreverse('') + 'b' -> None None + 'a' ==> TypeError
whereas for the first version:
# first version rreverse('ab') -> rreverse('b') + 'a' -> rreverse('') + 'b' -> '' '' + 'b' 'b' 'b' + 'a' 'ba'