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