CODEWITHSUNDEEP
pythonalgorithm
Jon
Jon

Reputation: 101

The mechanism to use recursion printReverse String

I am reading Explore - LeetCode.

It illustrate recursion with a simple but trick example printReverse

Let's start with a simple programming problem:

Print a string in reverse order.

You can easily solve this problem iteratively, i.e. looping through the string starting from its last character. But how about solving it recursively?

First, we can define the desired function as printReverse(str[0...n-1]), where str[0] represents the first character in the string. Then we can accomplish the given task in two steps:

  1. printReverse(str[1...n-1]): print the substring str[1...n-1] in reverse order.
  2. print(str[0]): print the first character in the string.

Notice that we call the function itself in the first step, which by definition makes the function recursive.

The implementation

import unittest
import logging 
logging.basicConfig(level=logging.DEBUG, format="%(levelname)s %(message)s")

def printReverse(s):
    helper(0, s)

def helper(idx, s):
    if s == None or idx >= len(s):
        return 
    logging.debug(f"index:{idx}")
    helper(idx+1, s)
    print(s[idx])

class MyCase(unittest.TestCase):

    def test_printReverse(self):
        s = 'string'
        printReverse(s)

unittest.main()

I am very confused with how it works. especially the first s[0] is not s but g.

$ python printReverse.py 
DEBUG index:0
DEBUG index:1
DEBUG index:2
DEBUG index:3
DEBUG index:4
DEBUG index:5
g
n
i
r
t
s
.
----------------------------------------------------------------------
Ran 1 test in 0.001s

OK

I am acknowledged that a calling stack is executing as 

def printReverse2(s):
    stack = []
    for c in s:
        stack.append(c)
    for c in stack:
        print(c)

However, the process is implicit, seems that there is not such step to put all characters to stack but instantly jump to for c in stack, print(c)

How could design a debugging to see the process of producing a calling stack? .

Upvotes: 0

Views: 51

Answers (1)

Filip Dimitrovski
Filip Dimitrovski

Reputation: 1726

You call printReverse('string') which calls helper(0, 'string'). And that's fine and clear.

But how do we get the result? The print(s[idx]) line should print s - the first character, right? But wait, the Python interpreter has to execute the previous line which is helper(idx+1, s) first.

Executing that statement means that Python has to pop the result value of that execution (in your case, helper doesn't return anything i.e. None) and in fact for each of t, r, i, n, g there's a new stack frame. How does that look like?

  1. You call the helper with helper(0, 'string')
  2. helper(0, 'string') frame waits for the result of helper(1, 'string') before it prints 'string'[0]' which is s.
  3. helper(1, 'string') frame waits for the result of helper(2, 'string') before it prints 'string'[1]' which is t
  4. ...
  5. helper(5, 'string') waits for the result of helper(6, 'string')
  6. helper(6, 'string') is a little bit different since 6 >= len('string'). The if is triggered, and it has a result None - it doesn't have to wait for anything!
  7. Now helper(5, 'string') has the result of helper(6, 'string') and proceeds to the print statement. The last character g appears on the screen.
  8. helper(4, 'string') has the result of helper(5, 'string') and can proceed to the print statement and you get a n.
  9. ... And so on
  10. ...Until you have the result of helper(1, 'string') and the original call helper(0, 'string') can print s.

You can use the pdb module to pause your Python program and execute it line-by-line.

Upvotes: 1

Related Questions