FAQ: Recursion vs. Iteration - Coding Throwdown - It Was Min To Be

Ah okay. I’ve now changed the code to this:

def find_min(my_list):
  if len(my_list) == 0:
    return None
  
  if len(my_list) == 1:
   result = my_list[0]
   print("result is " + str(result))
   return result

  if my_list[-2] < my_list [-1]:
    print("removing " + str(my_list.pop()))
    return find_min(my_list)
    #print(my_list)
  else:
    my_list.pop(-2)
    return find_min(my_list)
    #print(my_list)

print(find_min([1, 2, 3]))

and its all working.

That was very helpful thanks a lot.

I agree. Had to move on because a bigO for me doing this exercise became O(N^(‘inf’)).
Hope that the hint in the future will be more explanatory.

1 Like

So here is my solution. Albeit, a little different than the suggested solution, but I believe I am adhering to the requirement to use recursion and not iteration. Where am I going wrong. Btw, the code works for all the test cases given.

def find_min(my_list):
  if my_list == []: return None
  if len(my_list) > 1:
    if my_list[-1] > my_list[0]:
      my_list.pop()
    else:
      my_list.pop(0)
      find_min(my_list)
  return my_list[0]

# test cases
print(find_min([42, 17, 2, -1, 67]) == -1)
print(find_min([]) == None)
print(find_min([13, 72, 19, 5, 86]) == 5)

My Solution

def find_min(lst):
  n = len(lst)
  if n == 0:
    return None
  if n == 1:
    return lst[0]
  else:
    if lst[0] < lst[-1]:
      return find_min(lst[:-1])
    else:
      return find_min(lst[1:])

This is my solution. The two base cases are

  • if the list is empty or

  • if the list has only one element (which is the minimum no matter what)

The recursive calls then compare the first element of the list with the last element. And if the first element is smaller then the last we don’t need to look at this last element ever again - so we just need to look at the list without the last element lst[:-1]. For that smaller list we check again. Analogous if the last element is smaller then the first element.

After numerous recursive calls we end up with a list with just one element - that’s our min.

What is the purpose of ‘if not min’ in this code:

if not min or my_list[0] < min:
min = my_list[0]
return find_min(my_list[1:], min)

if WHAT ‘not min’?

1 Like

we don’t have to use comparison, we can also simply check something is truthy:

if True:
# or:
if "non empty strings are empty":

or falsy:

if False:
# or 
if "":

and with not, we flip the value (truthy becomes falsy and vice versa)

Then this line in the code should not work:

 if not min or my_list[0] < min:

At the beginning min = None so “if not None” should be false. And list[0] should always be more than None since in Python 3 any integer or float is > than None.

So this condition should never be met. Or do I miss something?

1 Like

None is falsy by itself:

if None:
  print("None is truthy")
else:
  print("None is falsy")

so not flips that, making it truthy

1 Like

Hello,
Can someone could explain me why I have an Recursion error?

def find_min(lst, min = None):
  if len(lst) == 0:
    return min
  else:
    if min == None or lst[0] < min:
      min = lst[0]
      lst.pop(0)
  return find_min(lst, min)

on the last line, you call the function from within the function, resulting in the function endlessly calling itself (recursion)

Ok, I figure out why my code was wrong, in adition of the wrong placment of the recursive return, I also didin’t return the right variable. Thanks for your support.

Hello,

Like the poster above, I solved with two bases cases:

  • If the list is len = 1, or;

  • If the list has two elements return the lesser of the two.

However, my approach incorporated a binary tree

Thought I believe I’ve met the requirement, I’m worried that I have massively over-complicated my approach. Are there any benefits to the way that I have solved this problem? Or did I end up making a rod for my own back?

Any help would be appreciated!

def find_min(list): if len(list) == 0: ValueError("Empty List") return None if len(list) <= 2: if len(list) == 1: return list[0] if list[0] < list[1]: return list[0] return list[1] middle_index = len(list) // 2 left_list = find_min(list[:middle_index]) right_list = find_min(list[middle_index:]) if right_list < left_list: low_value = right_list return low_value low_value = left_list return low_value # test cases print(find_min([42, 17, 2, -1, 67]) == -1) print(find_min([]) == None) print(find_min([13, 72, 19, 5, 86]) == 5) print(find_min([-1, 2, 3]) == -1)

Why wouldn’t the last step of the first list produce an index error. When list is [67] and then you call

return find_min(list_[1:], min_)

Wouldnt this result in an index error? There isn’t an [1] index

def find_min(list_=None, min_=None): if list_ == []: # base case return min_ else: if not min_ or (list_[0] < min_): min_ = list_[0] print("Passing list: {} and Min: {}".format(list_[1:], min_)) return find_min(list_[1:], min_) # test cases print(find_min([42, 17, 2, -1, 67]) == -1) print() print(find_min([]) == None) print() print(find_min([13, 72, 19, 5, 86]) == 5)

there is a typo in the exercise description/instructions:

find_mind([])
# None

should be find_min([])

*Should be noted that the typo is in the instructions, not in the code itself. So, a copyediting mistake.

You can submit a CQR to customer support (under help) or here in the forums under Feedback and Requests.