python-3.x - 将单一递归调用算法转换为分支、多重递归调用算法

Question

Write a recursive function longest_word(my_list) that takes a list of words (each in the form of a string) and returns the longest word in the list, using (at most) a single recursive function call from each function call. On an empty list, your function should return None.

Now see if you can rewrite the same function longest_word(my_list) using multiple recursive function calls instead.

我尝试了第一个问题，这很容易做。但是我想知道如何将单个递归调用转换为多个递归调用。除了正确的返回输出之外，多次递归函数必须被调用正确的次数，这意味着正确的运行逻辑对应于多次递归调用而不是单个递归调用，即使它们的输出结果本质上是相同的。

# First sample solution for single recursive calls
def longest_word(my_list):
    if not my_list:
        return None
    elif len(my_list) == 1:
        return my_list[0]
    else:
        l_word = longest_word(my_list[1:])
        if len(my_list[0]) > len(l_word):
            return my_list[0]
        else:
            return l_word

# Second sample solution for single recursive calls
def longest_word(my_list):
    l_word = _longest_word(my_list,'')
    if l_word == '':
        return None
    return l_word

def _longest_word(my_list, l_word):
    if not my_list:
        return l_word
    elif len(my_list[0]) > len(l_word):
        return _longest_word(my_list[1:], my_list[0])
    else:
        return _longest_word(my_list[1:], l_word)

可以将目前的两种解决方案修改为单个递归调用函数，得到多个递归调用函数。

这道题需要将列表分成两半，让它们同时运行，而不是一直运行到最后。

例如，您最好将它们包含在修改后的代码版本中

midpoint = len(my_list)//2
longest_word(my_list[midpoint:])
longest_word(my_list[:midpoint])

Answer 1

如评论中所述，这个问题很人为(但并非没有优点)。一个简单的解决方案是:

longest = max(len(x) for x in words)
longest_word = [x for x in words if longest == len(x)]
print(longest_word, longest)

运行时间是线性的(两次通过)，您可以通过避免列表理解和编写 for 循环轻松地一次完成。

但是，由于您需要使用多个递归调用，您可以采取 divide and conquer你提到的方法:

def longest_word(lst):

    # base cases
    if not lst:
        return ""
    elif len(lst) == 1:
        return lst[0]

    # recursive case
    mid = len(lst) // 2
    a = longest_word(lst[:mid])
    b = longest_word(lst[mid:])
    return a if len(a) > len(b) else b

words = ["cat", "dog", "mouse", "rabbit", "fox"]
print(longest_word(words))

在这里切片不是最优的(尽管它确实使代码简洁)；使用左右索引会更高效(读者练习)。随意索引元组以选择调用者中的单词或长度。

至于所采用的策略，可以将其视为一场比赛，两个词在每个括号中进行较量，以确定哪个更长。两个单词中较长的单词向上移动到下一轮。

       [dog vs rabbit]                  <- round 4
         |         |  
[cat vs dog]  [mouse vs rabbit]         <- round 3
  |      |       |         |
[cat]  [dog]  [mouse]  [rabbit vs fox]  <- round 2
                           |       |
                       [rabbit]  [fox]  <- round 1

时间复杂度为 O(n log(n)) 因为对于每个递归调用，我们将列表减半(类似于 merge sort )。另一种思考方式是，在锦标赛的每一轮(或调用树的每一级)中，有一半的参赛者被对手淘汰。