python - 递归函数不返回任何东西，即使它看起来像是要返回

Question

我正在尝试解决这个问题：

https://leetcode.com/problems/maximum-swap/description/

我的方法基本上是“检查您的号码中的第一个数字是否是最大的数字。如果不是，则将其与最大的数字交换。如果是，则将列表中的第一个数字放在一边（称为开头），然后对新号码（第一个数字被剪掉的那个）执行相同的程序。”

为此，我编写了一个名为 swapper 的递归函数，我在别处调用它。我给它输入了一个数字列表。如果它可以正常工作

def swapper(digits, beginning):
    print 'running: digits, beginning: ', digits, beginning
    if len(digits) > 0: #If there is anything left in the number, continue checking if the first digit is the largest)
        if digits.index(max(digits)) == 0:
            beginning.append(digits[0])
            print 'iterating: digits, beginning = ', digits[1:], beginning
            swapper(digits[1:], beginning) #recursively run the function with a smaller digit list
        else:
            digits[digits.index(max(digits))], digits[0] = digits[0], 
max(digits)
            return beginning + digits
    else: #If there is nothing left in the number, return the beginning list
          #which is just all the digits at this point
        print 'returning beginning'
        print 'beginning: ', beginning
        return beginning

#pseudocode here: digits = digits(digits of the number) 
results = swapper(digits, [])
print 'results: ', results

如果它从不点击交换器中注释的“else”，它会起作用，但如果它确实如此，它似乎不会返回任何东西。使用示例编号 9973，标准输出为：

running: digits, beginning:  [9, 9, 7, 3] []
iterating: digits, beginning =  [9, 7, 3] [9]
running: digits, beginning:  [9, 7, 3] [9]
iterating: digits, beginning =  [7, 3] [9, 9]
running: digits, beginning:  [7, 3] [9, 9]
iterating: digits, beginning =  [3] [9, 9, 7]
running: digits, beginning:  [3] [9, 9, 7]
iterating: digits, beginning =  [] [9, 9, 7, 3]
running: digits, beginning:  [] [9, 9, 7, 3]
returning beginning
beginning:  [9, 9, 7, 3]
results:  None

看起来它正确地将数字分区到开始列表中。然后它正确打印“开始：”，开始。该列表存在并且它是 [9,9,7,3] 就像我期望的那样。然后它应该返回那个。但是当我在函数之外打印结果时，它只是无。为什么？

它通过另一个 return 语句（说“返回开头 + 数字”的语句）正确返回。

标签： pythonrecursion

Answer 1

虽然您的函数在构建解决方案并深入递归时可以正常工作，但问题是当您在达到基本情况后开始返回时。到目前为止，您的代码不会将递归调用的结果传递回上面的调用。

您需要返回递归调用的结果。在您的情况下，将递归调用放在return前面。swapper(digits[1:], beginning)

这就是它的样子：

def swapper(digits, beginning):
    print 'running: digits, beginning: ', digits, beginning
    if len(digits) > 0: #If there is anything left in the number, continue checking if the first digit is the largest)
        if digits.index(max(digits)) == 0:
            beginning.append(digits[0])
            print 'iterating: digits, beginning = ', digits[1:], beginning
            # ADDED: return
            return swapper(digits[1:], beginning) #recursively run the function with a smaller digit list
        else:
            digits[digits.index(max(digits))], digits[0] = digits[0], max(digits)
            return beginning + digits
    else: #If there is nothing left in the number, return the beginning list
          #which is just all the digits at this point
        print 'returning beginning'
        print 'beginning: ', beginning
        return beginning

#pseudocode here: digits = digits(digits of the number) 
results = swapper([9, 9, 7, 3],[])
print('results: ', results)

输出：

running: digits, beginning:  [9, 9, 7, 3] []
iterating: digits, beginning =  [9, 7, 3] [9]
running: digits, beginning:  [9, 7, 3] [9]
iterating: digits, beginning =  [7, 3] [9, 9]
running: digits, beginning:  [7, 3] [9, 9]
iterating: digits, beginning =  [3] [9, 9, 7]
running: digits, beginning:  [3] [9, 9, 7]
iterating: digits, beginning =  [] [9, 9, 7, 3]
running: digits, beginning:  [] [9, 9, 7, 3]
returning beginning
beginning:  [9, 9, 7, 3]
results: [9, 9, 7, 3]