5
\$\begingroup\$

This is the code I wrote in order to find the smallest value in a list using recursion.However I feel like there would be a better way to do this?

def minimum(lst):
    """
    parameters : lst of type list
    return : the value of the smallest element in the lst
    """
    if len(lst) == 1:
        return lst[0]

    if lst[0] < lst[1]:
        lst.append(lst[0])
        return(minimum(lst[1:]))
    else:
        return(minimum(lst[1:])) 
\$\endgroup\$
3
\$\begingroup\$

Instead of adding back to the list to maintain an accumulator (the current minimum in this case), I'd just add a second parameter to the function, and allow it to default to None:

# acc, the accumulator, represents the current lowest found
def my_minimum(lst, acc = None):
   if not lst: # If the list is empty, return the current lowest
      return acc

   # Head is the first element, and the tail is the rest of the list
   # This is a common pattern when recursively iterating a list
   head, *tail = lst

   # The first time this is run, "not acc" fails, and it defaults to head
   new_acc = head if not acc or head < acc else acc

   return my_minimum(tail, new_acc)

lst = [2, 3, 4, 9, 2, -2]

print(my_minimum(lst))
-2

Note though that head, *tail = lst, is quite inefficient, as it requires making an entire copy to construct tail. I'm using it here for brevity.

\$\endgroup\$
  • \$\begingroup\$ what does the asterisk before tail do ? \$\endgroup\$ – Mister Tusk Nov 10 '18 at 20:23
  • \$\begingroup\$ It unpacks the rest of the list. That line is basically equivalent to head, tail = lst[0], lst[1:]. \$\endgroup\$ – Carcigenicate Nov 10 '18 at 20:27
0
\$\begingroup\$

Remove the else branch and push the last return statement to the same scope as the if-statement. Efficiency-wise, keep an eye on the stack size and memory use. Recursion is elegant but sometimes memory can grow exponentially if you are not careful.

\$\endgroup\$
0
\$\begingroup\$

It would be more efficient to not modify the list. If the first element is the smallest you now make n new lists. You need a parameter for the index of the minimum element found so far and the current index. If you don't want to modify the existing function you can make an inner function with the necessary params.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.