Home > database >  Recursion - Finding the longest string in a list
Recursion - Finding the longest string in a list

Time:10-11

Write a function recursiveLongestString(lst) that takes a list of strings as input and returns the longest string in the list. You may assume the list contains at least one element and there will not be a tie. This function must use recursion in a meaningful way; a solution that uses a loop or built-in max functions will receive no points. For example, recursiveLongestString(["a", "bb", "ccc"]) returns "ccc", and recursiveLongestString(["hi", "its", "fantastic", "here"]) returns "fantastic".

This is my code so far:

def recursiveLongestString(lst):

    if(len(lst)==1):
        return(lst[0])
    else:
        smaller= recursiveLongestString(lst[1:])
        if len(lst[0])<len(lst[1]):
                return smaller
        else:
            return lst[0]   smaller

I knos why its wrong, but cant seem to find a solution. Pls help

CodePudding user response:

You're very close. In the if/else you should only ever return a single string because thats what you want recursive_longest to ultimately return. Try this:

def recursive_longest(lst):
    if len(lst) == 1:
        return lst[0]

    current = lst[0]
    longest = recursive_longest(lst[1:])
    
    if len(current) < len(longest):
        return longest 
    else:
        return current

Bonus for you: You might also want to add an extra if statement at the beginning to decide what you might do if the list that was provided is empty.

CodePudding user response:

For a meaningful use, you could split the list in two and recurse left and right subsets of the list to determine two longest strings and then compare those two for the final result:

def recursiveLongestString(lst,start=0,end=None):
    if end is None: end = len(lst)-1 # initial range is whole list 
    if start==end: return lst[start] # base condition, stops recursion
    mid = (start end)//2             # split index
    maxLeft  = recursiveLongestString(lst,start,mid) # longest on the left
    maxRight = recursiveLongestString(lst,mid 1,end) # longest on the rigth
    return maxLeft if len(maxLeft)>len(maxRight) else maxRight


recursiveLongestString(["hi", "its", "fantastic", "here"])

'fantastic'

This has the advantage of not hitting the recursion depth limit when your list has close to 1000 items. Also, it doesn't create any copies of the list content

The reductive approach can be made more compact by transmitting the longest string down the recursion calls using a defaulted parameter:

def recursiveLongestString(L,S=""):
    return recursiveLongestString(L[1:],(L[0],S)[len(S)>len(L[0])]) if L else S
  • Related