Does anyone understand how this recursive function executes?

Question

This function computes the minimum number in a list recursively. Yes, I am already aware that there is a built in function that does so, but I am working on understanding how recursion works. However, I am unsure how this program executes to find that minimum number in the list. I was wondering if anyone could help me understand how this occurs.

def find_min(nums):

if nums == []: # base case 1
return None
if len(nums) == 1: # base case 2
return nums[0]
else: # if len(nums) > 1:
if nums[0] > find_min(nums[1:]):
return find_min(nums[1:])
return nums[0]

print(find_min([1, 3, 5, 2, 4, 6]))

print(find_min([1, 1, 1, 1, -1]))

print(find_min([]))

Answer 1

Principle of this recursive search can be more easily seen/understood by adding some print() to log values at different times:

https://code.sololearn.com/c69KQuo0uIDL/#py

The idea, is to think to your recursive function as it already works at writting time:

You need (have to write) a function returning the minimal value from a list, so you first write your base case 1 and 2 (if no items no result, if unique item result is necessarly the unique one)... and your defaut case (if list length > 1) will get the first item of the list to search, and compare it with... the result of your min search function, applied to the list to compare minus its first element (slice notation [1:] will get from index 1 -- 2nd item -- to end): recursively, you will necessarly end by passing a unique item list, wich will be the base case 2, so your function can solve it and return the minimal value ^^

Backwards with returned recursive value, you can test if first indexed value is geater or lesser than the unknown minimal value of the sublist got by recursive function call ;)

Check the code (and obviously its output) I've linked to see how helpful can be some log print()...

Answer 2

Interesting approach to the problem.

The first base case just makes sure you have a reasonable list (input verification). The second is the true recursion base case: if you only have element in your list, it is by definition the smallest.

The next bit is a little dizzying. At each stage, your focus is on the first element vs the smallest element in the rest of the list that you were given. Whichever is smaller, return that.

But how do you find the smallest element of the remaining list? Redo the procedure, but with the first element stripped out of the list. Then you compare the 2nd element to the rest of the list.....this continues until you have only one element left. You return that element, then step back up the chain of comparisons that you have on hold.

Each of those if statements will give you the smaller element at that stage, so when you are all done, you end up with the smallest element of the original list.

I can't see the example lists you had anymore, unfortunately, so I'll make my own up. [9,2,6,5]

Which is smaller:
9 or:
2 or:
6 or:
5

5 is smaller than 6, return 5
2 is smaller than 5, return 2
2 is smaller than 9, return 2

And there we have it: 2 is the minimum value odd the list.

Remember: whenever you make a recursive function call, the current state of the program is frozen and saved until that call is resolved. So in this case, you don't actually do any of the less than checks until you walk through the whole list.

Hopefully that didn't make things more confusing...

Answer 3

similar to loop

Answer 4

While the code could be a bit more efficient (using a local variable to avoid 2 recursive calls, for instance), there's nothing wrong with it that a bit of explanatory commenting wouldn't solve.

Answer 5

Probably do the recursive call first, and save the result in a variable. Then if(a<b) return a else return b.

There might be other ways too, bit it's getting late for me...

Answer 6

@marek actually true but i can't stop laughthing

Answer 7

The use of a local variable to avoid twice recursive call is what I've done and commented in the script I(ve previously linked... if you check it ^^

Answer 8

some real haters in here btw

Answer 9

Yeah its getting late for me too.

Thank for explaining that. I think it makes sense!

Answer 10

Thank you both for some awesome answers and advice.

Answer 11

Yeah I did I'll probably look more into it tomorrow once I can get back on my computer instead of my phone. Thanks though for your input and help if a novice coder like me!

Answer 12

try to imagine a load of bricks to carry to another place. How to do that? If it's too heavy then carry half of it. If it's too heavy...

Answer 13

@Jamie wrote:

<< This was quite a challenge to solve elegantly, ie no globals. @visph, you did a good job, so this is *not* a contest, I just saw it as a personal challenge to solve more elegantly. My code takes a list as an argument, ascertains the data needed and recursively calls itself the duration of the list >>

I don't know what's particularly elegant to do without globals ^^ Golbal variables are bad practice only when missused: I will contrarly tend to think that in such case of recursive function, keeping the lesser number of local variables and arguments will spare memory consumption (and also improve speed), even if in that case (ie get min value) recursion isn't the most efficient solution anyway ;P

Answer 14

@visph: I totally agree with you about optimization and globals. If globals are better suited, use them. I just wanted to challenge myself within the "confines" of so-called good practice. I think you'll find our codes run more or less the same. Mine may use a little more resources on memory, yours may on CPU (I'm no expert but there's an extra CMP and more math in yours). Yes, probably yours can recurse deeper in an interpreted language because I used local variables, but really I'm not trying to compete. I wasn't trying to say it was better, just elegant (as in pretty, easy to follow). I highly doubt my code is better than anybody's because I'm new here, only 2.5 months old so I know very little. Perhaps my wording was bad. Sorry for any offence, I was just seeing it as fun so that is why I posted not to think I was being arrogant by posting code when you had already answered the question. I was just having fun coding.

Answer 15

Yeah it also probably isn't the best way to save the problem. I know they're might be even a better way to write this recursive function

Answer 16

Yeah btw how would you use a local variable to do such a thing?

Answer 17

Off topic, but please try out my code. its fun!

https://code.sololearn.com/WCnNImldl210/?ref=app

Answer 18

its simply call the function many times but iam agree with you its hard to learn than other type

Answer 19

hello nK to u Ho kuch b vo nb ik ji ki

Answer 20

This was quite a challenge to solve elegantly, ie no globals. @visph, you did a good job, so this is *not* a contest, I just saw it as a personal challenge to solve more elegantly. My code takes a list as an argument, ascertains the data needed and recursively calls itself the duration of the list:
https://code.sololearn.com/c5t6V5h0vy21/?ref=app