0

I need to reverse a string using recursion, I was able to accidentally write a code that successfully accomplishes the task, but I don't really understand why. Here's what I have

import stdio
import sys


# Entry point
def main():
    s = sys.argv[1]
    stdio.writeln(_reverse(s))


# Returns the reverse of the string s.
def _reverse(s):
    # Base case: if s is the empty string, return an empty string.
    if len(s) == 0:
        return ""
    # Recursive step: return last character in s + _reverse(s excluding last character).
    else:
        return s[-1] + _reverse(s[:len(s)-1]) 


if __name__ == '__main__':
    main() 

This makes sense to me just for the first recursive call. Lets say the input is "Bolton" the length of this string is 6, the first recursive call would simply call the _reverse function on s [0:5] What I don't understand is that how do the next recursive calls work? Because len(s) would remain the same? To my understanding, each recursive call to the _reverse() would subtract 1 from len(s) -- which is 6. Can someone please explain why thats not the case? How does the the len decrement?

1
  • 1
    Each of the calls to _reverse() has its own private value of s, each of which has a different length. Commented Nov 18, 2022 at 3:21

1 Answer 1

1

s[:len(s)-1] or the same value but shorter s[:-1] is essentially a string with the last element removed, the length of it is 1 shorter than the original. You then call the function with that shorter string.

So a step by step resolution would look something like this:

reverse("hello") # len("hello") != 0 so we substitute with else
"hello"[-1] + reverse("hello"[:-1])
"o" + reverse("hell")
"o" + "hell"[-1] + reverse("hell"[:-1])
"o" + "l" + reverse("hel")
"o" + "l" + "hel"[-1] + reverse("hel"[:-1])
"o" + "l" + "l" + reverse("he")
"o" + "l" + "l" + "he"[-1] + reverse("he"[:-1])
"o" + "l" + "l" + "e" + reverse("h")
"o" + "l" + "l" + "e" + "h"[-1] + reverse("h"[:-1])
"o" + "l" + "l" + "e" + "h" + reverse("") # len("") == 0 so we substitute ""
"o" + "l" + "l" + "e" + "h" + ""
"olleh"
Sign up to request clarification or add additional context in comments.

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.