[ recursive function does not return value ]

The recursive function doesn't seem to return a value. This is a modified version of a snippet i saw in a data structures book by Goodrich. However, if the return statement is changed to a print statement and the assignment to x is removed, the result is printed correctly to screen. Any ideas why?

def reverse(S, start, stop):
    if start < stop - 1:
        S[start], S[stop-1] = S[stop-1], S[start]
        reverse(S, start+1, stop-1)
    else:
        return S


if __name__ == "__main__":
    x = reverse([1, 2, 3], 0, 3)
    print x

Answer 1

Very close.

Consider:

def reverse(S, start, stop):
    if start < stop - 1:
        S[start], S[stop-1] = S[stop-1], S[start]
        return reverse(S, start+1, stop-1)   # This should return as well
    else:
        return S


if __name__ == "__main__":
    x = reverse([1, 2, 3], 0, 3)
    print x

Output:

[3, 2, 1]

Not only should your base case return something, but in cases where your recursive algorithm isn't the base case, you should return the output of the recursive call.

Answer 2

You missng return I think:

def reverse(S, start, stop):
    if start < stop - 1:
        S[start], S[stop-1] = S[stop-1], S[start]
        return reverse(S, start+1, stop-1)
    else:
        return S

This will result in: [3, 2, 1]