将单个递归调用算法转换为分支式、多个递归调用算法

Question

将单个递归调用算法转换为分支式、多个递归调用算法

3

写一个递归函数longest_word(my_list)，它接受一个单词列表（每个单词都是字符串形式），并返回该列表中最长的单词，每次函数调用最多使用一个递归函数调用。如果列表为空，则函数应返回None。

现在看看是否可以使用多个递归函数调用重写longest_word(my_list)函数。对于正确的返回输出，多个递归函数必须被调用正确的次数，这意味着其运行逻辑需要相应地针对多个递归调用而不是单个递归调用，即使它们的输出结果本质上相同。

# 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])

- mbjerry

欢迎来到SO！max([len(word) for word in my_list])有问题吗？这段代码似乎过于复杂，去解决一个简单的任务。 - ggorlen

列表推导式是可以接受的，你需要根据单词的长度返回列表中的单词，有点像在字典中根据值返回键。但是我的问题关键在于从单个递归调用转换为多个递归调用，也就是说要将过程“分裂”成两个部分（同时运行一半和一半），而不是一直沿着一个方向运行到结束。 - mbjerry

我错了，你是对的，它们不应该同时运行。但我认为在这里使用多个递归调用的基本思想是分别找出列表的前半部分和后半部分中最大长度的单词，然后比较它们并选择长度较长的那个，而不是直接获取结果。我的意思是，我现在的问题是运行逻辑看起来比结果、代码简洁和其他方面更重要。 - mbjerry

明白了。由于基本解决方案非常朴素直接，附加要求有点难以理解和相当混乱。我会尝试回答，如果我错了，请随时纠正我。 - ggorlen

坦白地说，这是我计算机作业中的一个奖励问题，其代码将在特定平台上运行和测试，以检查预期输出结果和运行模式是否都符合要求（他们设置了一系列测试来测试您的代码），我尝试了很多次但都失败了，这就是为什么我渴望寻求帮助的原因。谢谢伙计。 - mbjerry

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- ggorlen · Accepted Answer

正如评论中所提到的，这个问题相当人为（但也不是没有价值）。一个简单的解决方案是：

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

运行时间是线性的（两次通过），如果避免列表推导式并编写一个 for 循环，您可以轻松地在一次通过中完成。

然而，由于需要使用多个递归调用，您可以采用分治的方法，就像您提到的那样：

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))，因为对于每个递归调用，我们将列表减半（类似于归并排序）。另一种思考方式是，在比赛的每一轮（或每个调用树的级别）中，一半的选手被对手淘汰。