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

This community-built FAQ covers the “It Was Min To Be” exercise from the lesson “Recursion vs. Iteration - Coding Throwdown”.

Paths and Courses
This exercise can be found in the following Codecademy content:

FAQs on the exercise It Was Min To Be

There are currently no frequently asked questions associated with this exercise – that’s where you come in! You can contribute to this section by offering your own questions, answers, or clarifications on this exercise. Ask or answer a question by clicking reply () below.

If you’ve had an “aha” moment about the concepts, formatting, syntax, or anything else with this exercise, consider sharing those insights! Teaching others and answering their questions is one of the best ways to learn and stay sharp.

Join the Discussion. Help a fellow learner on their journey.

Agree with a comment or answer? Like () to up-vote the contribution!

Found a bug? Report it!

Have a question about your account or billing? Reach out to our customer support team!

None of the above? Find out where to ask other questions here!

Hello!
I am wondering why this code does not work:

``````def find_min(my_list):
min = None
if len(my_list) == 0:
return min
while len(my_list) > 0:
element = my_list[0]
print(my_list)
print(element)
if min is None:
min = element
elif element < min:
min = element
my_list.remove(element)
find_min(my_list)
return min
``````

When calling print(find_min([4, 9, 2]))
it returns 4 and prints:

[4, 9, 2]
4
[9, 2]
9
[2]
2
4

Somehow, it fails to replace 4 with 2 as the min value.

You are using both a loop and recursion? Use one or the other, not both.

your loop only makes a single iteration, then the function gets called again (which will set min to None again).

i highly recommend this tool:

http://www.pythontutor.com/visualize.html

to walk through your program, so you can see the strange flow that is happening in your program

1 Like

Why not doing?

``````def find_min(my_list):
return min(my_list) if my_list else None
``````

I also use min for the recursion:

``````def find_min(my_list):
if not my_list:
return None
if len(my_list) == 1:
return my_list[0]
return min(my_list[-1], find_min(my_list[:-1]))
``````

The test are too strict or incorrect.

Define `find_min()` so that it uses RECURSIVE calls. Do not use iteration!

``````#Implement your version of find_min() which has the same functionality using recursive calls!
def find_min(l):
if not l:
return None
else:
return l[0] if l[0] == min(l) else find_min(l[1:])

# 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]) == 1)
``````

calling min is pretty objectional, once you’ve done that you already have the answer and would need to do nothing else

also, you’re copying the lists so you’re getting a time complexity of `O(N * N)` instead of `O(N)`

To clarify, the error message is accurate, it’s triggered by that your function immediately returns the result without recursing for the rest when the first value is the smallest - it’s cheating by looking at the answer as reported by min.

My solution.

If the second-to-last element is larger than the last, swap then, then recursively call with a list of one less length

``````def find_min(my_list):
if not my_list: return None
elif len(my_list) == 1: return my_list[0]

if my_list[-2] > my_list[-1]:
my_list[-2] = my_list[-1]

return find_min(my_list[0 : -1])
``````

obtaining min shouldn’t destroy the data, and you don’t need to - you already have arguments and return values for communication

``````xs = [2,1]
print(f'xs before: {xs}')
res = find_min(xs)
print(f'result: {res}')
print(f'xs after: {xs}')
``````

it’s also copying the list during each iteration, which is a bit much work (makes it quadratic instead of linear execution time)

``````from datetime import datetime

xs = [1] * 950
time_builtin = datetime.now()
min(xs)
time_builtin = datetime.now() - time_builtin

time_find_min = datetime.now()
find_min(xs)
time_find_min = datetime.now() - time_find_min

print(f'time for min: {time_builtin}')
print(f'time for find_min: {time_find_min}')
``````

it takes many times more time than the built-in. slower is expected, but not by such a large factor. this gets worse with larger input, but you’ll hit the recursion depth limit before that

it’ll reach maximum recursion depth very quickly, so it’ll only operate on small lists, it’s possible to get a max depth of `log N` which would make the depth fairly low even for very large input

``````find_min([1] * 1000)
``````

So what you’d want to do instead is to say that the minimum of the overall thing is the smallest of the current value and the minimum of the rest.

To avoid copying, you can use indices instead of a list. So you’d specify the start location.

But you’ll also recurse as deep as the list is long, and you only get about 1000 depth. To solve that, you can recurse on each half. By splitting the input in half, the depth becomes half as much too, but you do it twice so you end up with the overall same thing. And it’s not just half, it’s half at each level. How many times do you have to halve a list to get it to size 1? log N times. log N will therefore be the max depth.

It’s also worth noting that minimum is a specialization of reduce.
There’s an initial value, you combine each value into the accumulated result by keeping the smaller one. Reduce can do the same thing with splitting the input in half, the overall order is still left to right provided that the left half is done first and then the right half. (in the case of min though, the order does not matter)

You might want to use two functions, one for accepting input and checking for empty, and another that has a different signature involving indices instead of lists.

1 Like

Thank you for trying to explain all this. I just moved on. The course was aggravating me an maybe in the future I’ll revisit it after I forget about this.

1 Like

Here is my solution.

``````def find_min(my_list):
if len(my_list)== 0:
return None
if len(my_list)==1:
return my_list[0]
elif my_list[0]>= my_list[1]:
return(find_min(my_list[1:]))
else:
my_list.pop(1)
return(find_min(my_list))
# test cases
print(find_min([42, 17, 2, -1, 67]))
print(find_min([]) == None)
print(find_min([13, 72, 19, 5, 86]) == 5)
``````
1 Like

There is something that I don’t understand. Maybe it’s something already explained. In the solution code, what does `not my_list` mean?

1 Like

empty lists have a falsy value, while list with values have a truthy value.

so `not` will flip the value, so this essentially makes sure None is returned when the list is empty

you could also do:

``````if my_list == []:
``````
1 Like

Then, shouldn’t it be

``````if my_list:
``````

Because if my_list is empty, then it will be None, which would return False. Otherwise, it would return True.
?

Also, possible, then in else clause return None

i prefer using `if not my_list` though, that flow of catching the empty list scenario feels more logical. But both work

the condition is there to catch empty list and return a specific value in that case.

2 Likes

The iterative definition of this problem in Codecademy has a bug
If you pass a list that contains the element 0, it totally messes up the function,
and the wrong minimum is returned. For example,

``````find_min([13, 72, 19, 5, 0, 86])
``````

returns 86 as the minimum element, instead of 0

The method definition should be:-

``````def find_min(my_list):
min = 0
for element in my_list:
if element < min:
min = element
return min
``````

tried the code:

works as expected?

Hi all having an issue in this exercise I need some help with:

This is my code:

``````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))
for i in my_list:
return i

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

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

When I run the code I expected to get 1 as the result of the call of:

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

Instead I get as the printout:

``````removing 3
removing 2
result is 1
None
``````

as you can see I get None as the return value not 1.

Can anyone explain this to me?

`return i` hands back data to the caller:
``````    print("removing " + str(my_list.pop()))