Convert single recursive call algorithm to a branching, multiple recursive call algorithm

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.

I tried the first problem which is quite easy to do. However I wonder how to convert the single to multiple recursive calls. In addition to the correct return output, the multiple recursive function must be invoked the correct number of times, which means the correct running logic corresponding to multiple recursive calls instead of single ones, even if their output results are essentially the same.

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

You can modify the current two solutions for single recursive calls function to get multiple recursive calls function.

This question requires to split the list into two halves to have them run simultaneously rather than having one running all the way through to the end.

For example, you'd better include them in the modified version of code

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

Answer 1

As mentioned in the comments, the problem is pretty contrived (but not without merit). A simple solution is:

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

Running time is linear (two passes), and you could easily do it in one by avoiding list comprehensions and writing a for loop.

However, since you are required to use multiple recursive calls, you can take a divide and conquer approach as you mentioned:

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

Slicing here is not optimal (although it does make the code succinct); using left and right indices would be more performant (an exercise for the reader). Feel free to index into the tuple to pick the word or length in the caller.

As for the strategy that's being employed, think of it as a tournament where two words battle in each bracket to determine which is longer. The longer word of the two moves up the tree to the next round.

       [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

Time complexity is O(n log(n)) because for each recursive call, we cut the list in half (similar to merge sort). Another way of thinking about it is that half of the contestants are eliminated by their opponents in each round of the tournament (or each level of the call tree).