Reversing a list recursively, I don't understand the output

Question

Hi, I am a little confused on why the output for ans is 'hello' when I am trying to reverse the list using this recursive method. According to the debugger, ans is correct in the function, but suddenly changes when it exits the rs function.

Did you not read the "Do not return anything" part of the problem? The correct answer in `ans` is irrelevant, that's not what is being checked. — jasonharper, Jun 22 '22 at 14:30
Read your instructions in the docstring, they're *very* explicit: "Do not return anything, modify s in-place instead." You did the *exact* opposite of what the instructions called for. — ShadowRanger, Jun 22 '22 at 14:30
You're making it too complex - just do a `swap` on the string. — Daniel Hao, Jun 22 '22 at 14:35
Are you actually required to use recursion? Restricted from using `list` methods or slicing? Because in real code, with a guaranteed `list` input, the body of the function would just be `s.reverse()`, and that's it. — ShadowRanger, Jun 22 '22 at 14:37
[Please don't post screenshots of text](https://meta.stackoverflow.com/a/285557/354577). They can't be searched or copied, or even consumed by users of adaptive technologies like screen readers. Instead, paste the code as text directly into your question. If you select it and click the `{}` button or Ctrl+K the code block will be indented by four spaces, which will cause it to be rendered as code. — ChrisGPT was on strike, Jun 22 '22 at 17:29

score 1 · Answer 1 · edited Jun 22 '22 at 14:48

1

A few observations:

reverseString() is supposed to have return type of None, so the line return ans is not needed
the logic for ans looks fine, but based on the comment reading "Do not return anything, modify s in-place instead", you need to modify s; you can do this using the (slightly cryptic) statement s[:] = ans, which (thanks to the : character) replaces the contents of s with those of ans
speaking of : syntax, this is not critical, but you can use s[1:] (just one :) instead of s[1::]

Updated code (I have assigned List to be list, to preserve the def statement of reverseString()):

List = list
class Solution:
    def reverseString(self, s: List[str]) -> None:
        ans=[]
        def rs(s, ans):
            if len(s) == 0:
                return
            a = s[0]
            rs(s[1:], ans)
            ans.append(a)
        rs(s, ans)
        s[:] = ans


x = Solution()
s = [c for c in 'hello']
print('input:', s, sep='\n')
x.reverseString(s)
print('output:', s, sep='\n')

Output:

input:
['h', 'e', 'l', 'l', 'o']
output:
['o', 'l', 'l', 'e', 'h']

edited Jun 22 '22 at 14:48

mkrieger1

19,194
5
54
65

answered Jun 22 '22 at 14:31

constantstranger

9,176
2
5
19

1

`s = ''.join(ans)` does not modify `s` in-place (not in any useful way, nor the way the exercise definitely requires), it *replaces* the local binding of `s` with a binding to a new object. The caller's `list` remains unmodified. Even if you want to cheat like this (making a new `list`, then replacing the contents), you'd need to do something like `s[:] = ans` to replace the *contents* of `s` without rebinding it. – ShadowRanger Jun 22 '22 at 14:32
OR try this in-place way too: ` for i in range(len(s) // 2):` `s[i], s[~i] = s[~i], s[i]` – Daniel Hao Jun 22 '22 at 14:33
1

@DanielHao: Cute, though if you're discarding recursion, you may as well just make the entire body of the function `s.reverse()`. It is a `list` after all. :-) – ShadowRanger Jun 22 '22 at 14:35
Sure. Agreed. But the `interviewer` will not be very happy.... ;-) – Daniel Hao Jun 22 '22 at 14:36
@ShadowRanger Good catch. I carelessly misread the question: I now see that the input is a list, not a string (despite the method having the name `reverseString()` ...). I have updated my answer. Note that rather than seeking an optimal solution, I have tried to stay close to OP's original algorithm to hopefully aid in understanding. – constantstranger Jun 22 '22 at 14:47

Reversing a list recursively, I don't understand the output

1 Answers1