Why do I need both condition branches for the rreverse function?

Question

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[0]

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[0]

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?

Thank you!

Because if the string is empty, then there is no `s[0]`, but this is a terrible way to do it. — Willem Van Onsem, Sep 25 '18 at 11:41
There's a much shorter way to reverse a string in Python by using ``s[::-1]``. — DocDriven, Sep 25 '18 at 11:46
@Willem `[0]` is not the issue, that is always guarded against. It would also produce an `IndexError` instead of a `TypeError`. — deceze, Sep 25 '18 at 11:47
@deceze: the question in the title is "Why is this `s == ""` necessary, it is necessary since for an empty string, it will indeed result in an `IndexError`, I did not talk about a type error. The point is that using this recursion is really bad. Not only is it inefficient, but the call stack will scale linear. — Willem Van Onsem, Sep 25 '18 at 11:48
@DocDriven indeed, but that's not how you will learn recursion ;-) — bruno desthuilliers, Sep 25 '18 at 11:49
@Willem Ah, *that's* what you specifically responded to. That wasn't very clear. And sure, this isn't terribly efficient by any means; I'd expect it to be for practicing recursive functions. — deceze, Sep 25 '18 at 11:50
@PaulRooney Thank you, I forgot my recursion requires a base case. — Hilla Shahrabani, Sep 25 '18 at 11:55

score 6 · Answer 1 · answered Sep 25 '18 at 11:41

6

the problem with the second construct is that if s is the empty string, the function returns None which isn't a string, and the end-caller expects a string, even empty, so returning None will make the caller code break (which leads to questions like Why does my function return None?)

You could write it with a ternary expression to make sure that it returns something whatever the value of x

def recur_reverse(x):
    return recur_reverse(x[1:]) + x[0] if x else ""

answered Sep 25 '18 at 11:41

Jean-François Fabre

137,073
23
153
219

1

`return recur_reverse(x[1:]) + x[0] or ""` – Chris_Rands Sep 25 '18 at 11:48
Thank you for your explanation. So you're saying it will not work when I call the function on any string even if it does contain 2+ characters for it to process as it should? – Hilla Shahrabani Sep 25 '18 at 11:49
@Chris_Rands no. Because if `x` is empty the left expression breaks. – Jean-François Fabre Sep 25 '18 at 11:50
@HillaShahrabani `x[1:]` returns empty string if the string has 0 to 1 char. I don't see why it wouldn't work. But I didn't try. – Jean-François Fabre Sep 25 '18 at 11:51
1

oh yah, could use `x[0:1]` instead – Chris_Rands Sep 25 '18 at 11:53
I fear that it will also call `recur_reverse` in an infinite recursion with an empty string to compute ... an empty string. – Jean-François Fabre Sep 25 '18 at 11:59

score 5 · Answer 2 · answered Sep 25 '18 at 11:48

When a Python function reaches the it's last statement without an explicit return statement, it implicitely returns None. In your second example:

def recur_reverse(x):
    if x != "":
        return recur_reverse(x[1:]) + x[0]

when x is actually the empty string, the if branch is skipped and execution continues with "the next statement" - but since there's no "next statement" (you've reached the function's end), the function returns None. With the recursive calls, you always end up calling the function with an empty string, so the function returns None, and as the error messages says, you cannot concatenate None with a string (for very obvious reasons).

score 4 · Accepted Answer · answered Sep 25 '18 at 11:56

In the recursion, you each time "pop" the first element s[0] from the string s, and you append it to the reverse of the remaining elements rreverse(s[1:]).

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[0], 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[0]

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 None instead.

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'

This is a wonderful explanation. Thank you for taking the time to make this issue clearer. :) — Hilla Shahrabani, Sep 25 '18 at 12:11

score 3 · Answer 4 · answered Sep 25 '18 at 11:41

3

because you do not specify what happens, when x = "". this leads to an error if x is indeed an empty string, because then your function returns type None, which is unexpected by the caller.

answered Sep 25 '18 at 11:41

Cut7er

1,209
9
24

runz0rd · Answer 5 · 2018-09-25T13:16:41.033

0

The second one is not returning anything for cases other than x != "", so when you do recur_reverse(x[1:]) that might not return anything (None)

edited Sep 25 '18 at 13:16

answered Sep 25 '18 at 11:44

runz0rd

126
5

Why do I need both condition branches for the rreverse function?

5 Answers5