使用递归printReverse String的机制

Question

我正在读Explore - LeetCode。

它用简单但技巧的例子printReverse来说明递归

让我们从一个简单的编程问题开始：

以相反的顺序打印字符串。

您可以轻松地迭代地解决此问题，即从其最后一个字符开始循环遍历字符串。但是如何递归地解决它呢？

首先，我们可以将所需的函数定义为printReverse(str[0...n-1])，其中str[0]表示字符串中的第一个字符。然后我们可以分两步完成给定的任务：

1. printReverse(str[1...n-1])：以相反的顺序打印子字符串str[1...n-1]。
2. print(str[0])：打印字符串中的第一个字符。

请注意，我们在第一步中调用函数本身，根据定义，它使函数递归。

实施

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()

我很困惑它是如何工作的。特别是第一个s [0]不是s而是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

我承认调用堆栈正在执行

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

但是，这个过程是隐含的，似乎没有这样的步骤可以将所有字符叠加但是立即跳转到for c in stack, print(c)

如何设计调试以查看生成调用堆栈的过程？ 。

Answer 1

你打电话给printReverse('string')，它叫helper(0, 'string')。这很好，很清楚。

但是我们如何得到结果呢？ print(s[idx])线应该打印s - 第一个字符，对吗？但等等，Python解释器必须首先执行前一行helper(idx+1, s)。

执行该语句意味着Python必须弹出该执行的结果值（在您的情况下，帮助程序不返回任何内容，即None），实际上每个t, r, i, n, g都有一个新的堆栈帧。这看起来怎么样？

1. 你用helper(0, 'string')给助手打电话
2. helper(0, 'string')框架在打印helper(1, 'string')之前等待'string'[0]'的结果，这是s。
3. helper(1, 'string')框架在打印helper(2, 'string')之前等待'string'[1]'的结果，这是t
4. ...
5. helper(5, 'string')等待helper(6, 'string')的结果
6. helper(6, 'string')与6 >= len('string')有点不同。 if被触发，它有一个结果None - 它不必等待任何东西！
7. 现在helper(5, 'string')有helper(6, 'string')的结果并继续进行print声明。最后一个字符g出现在屏幕上。
8. helper(4, 'string')有helper(5, 'string')的结果，可以继续打印声明，你得到一个n。
9. ... 等等
10. ...直到你有helper(1, 'string')的结果和原始的电话helper(0, 'string')可以打印s。

您可以使用pdb模块暂停Python程序并逐行执行。