-2

I have the below code which takes and reverses a string. I can't understand a part from debugging the code. When the string length is being equal to 0, it goes into the if branch and returns string, immediately after that, the debugger goes into the else branch and regularly returns letters.

Please explain how is it that the code jumps from if statement into the else and regularly returns letters.


def func(mString: str):
    if len(mString) == 0:
        return mString

    else:
        print("Once")
        return func(mString[1:]) + mString[0]


reversed_str = func("Hello")
print(reversed_str)

Tried to debug to see how it works but couldn't understand

David
  • 27
  • 5
  • 1
    The function calls itself. Exactly like when you call _any_ function from _anywhere_, when that function returns your code continues from where the call was made. There is nothing inherently magical or special about recursion. – paddy Mar 18 '23 at 03:50
  • 1
    No it doesn't. Recursion doesn't run "in the same function", every time you recurse you start a _new_ function call, like a giant chain where every part of the chain is the same function but called with different input. When a return happens, you leave the current function call, and the code picks up where you left the previous function call. – Mike 'Pomax' Kamermans Mar 18 '23 at 03:51
  • And see this [accepted answer to another duplicate](https://stackoverflow.com/a/13708714/15032126). – Ignatius Reilly Mar 18 '23 at 04:11
  • Each function call has to wait until the next call is returning something. So, the _first one to return something_ is the base case (i.e. the code from the `if` statement). – Ignatius Reilly Mar 18 '23 at 04:14
  • Please see the bold text where my question is, I can understand recursion but I don't understand how it jumps from if branch to else and returns letters one by one. – David Mar 18 '23 at 04:40
  • `'a'[1]` -> `IndexError`, However `'a'[1:]` -> `''`. So the last call (the first one to return something) is taking a string of len == 0. – Ignatius Reilly Mar 18 '23 at 16:16

2 Answers2

1

Visual explanation:

                                  func('foobar')
                             func('oobar') + 'f'
                        func('obar') + 'o'
                   func('bar') + 'o'
              func('ar') + 'b'
         func('r') + 'a'
    func('') + 'r'
          ''
# ------------------------------------------------ #
          '' + 'r' + 'a' + 'b' + 'o' + 'o' + 'f'
                                        'raboof'
InSync
  • 4,851
  • 4
  • 8
  • 30
0

[![How this code work:][1]][1]

After if statement being executed, the control will goes back to the statement where from it was jump to if statement that is else statement and remaining code will be executed that is concatenate the last character in this case and rest of the flow will go like this until it goes to the first return statement and the output will be returned altogether.

Important: Recursion uses Stack Data Structure. and In stack data structure it works as first in last out, because the function which will go last into the stack will be executed first and result will be returned to the second last function and executed and again result will be returned to the third last function in the stack and so on until that last function which was come first into the stack will execute and return the final output. [1]: https://i.stack.imgur.com/sSCnM.jpg

Nitiz
  • 64
  • 4