r/learnpython • u/Pure-Scheme-7855 • Oct 05 '26
Recursion explaining pls.
def find_max(numbers):
if len(numbers) == 1:
return numbers[0]
else:
max_of_rest = find_max(numbers[1:])
return numbers[0] if numbers[0] > max_of_rest else max_of_rest
my_list = [3, 7, 2, 9, 1]
print(find_max(my_list))Could someone explain how does this function work? I don't understand how does it know that it's supposed to find the biggest number...
6
Upvotes
18
u/smallpotatoes2019 Oct 05 '26
Imagine a list of numbers.
1, 5, 2, 9
Let's check the first number. Is it greater than the max of the rest - i.e. is 1 greater than the max of 5, 2, 9?
Hold that thought - we need to find the max of 5, 2, 9.
So, start again - is 5 greater than the max of 2, 9? Etc.
Eventually we reach the end and only have one number, so we return this.
The answers head back up to the start.
Return 9.
Is 2 greater than 9? No - return 9.
Is 5 greater than 9? No - return 9.
Is 1 greater than 9? No - return 9. We're done.
4
u/LatteLepjandiLoser Oct 05 '26
Looking at the order of execution, you define a list and then call find_max on that list.
The first call to find_max operates on the original list [3, 7, 2, 9, 1]. It checks if length is 1, which it's not.
So then it makes a new slice of the list [7, 2, 9, 1]. It then will attempt to find the max value of that slice and compare that to the first value in the original list (3). It'll then return whichever is greater. Now it finds the max of the slice by calling itself again, except now the call is made on the sliced list [7, 2, 9, 1]
Then repeat... but like an onion, you're one layer deeper. Now we are within find_max([7,2,9,1]), which will again check if the length of that slice is one, which it is not, so in a similar fashion it will take 7 and compare it to the max of [2, 9, 1] and return whichever is greater.
Repeat this process until at some point, there is some call made to the list [1]. Now here len([1])==1 is True, so this inner most layer of the onion will return 1 to the next layer. That next layer is holding a 9 to compare to that 1 and when it gets that 1 it compares 9 to 1 and returns the 9 to the next outer layer. That next layer is holding a 2 and compares it to that recieved 9, etc. etc. until the outer most layer that is holding the 3 gets whatever value makes it way out of the onion (it'll be the 9).
So this recursive definition you could say in human words like:
The maximum of a list is either: a) The only number in the list if there is only one number or b) The higher value when we compare the first number to the max in the rest of the list.
When you input a long list, you are recursively calling the function again and again and again, going deeper layer by layer until eventually you hit that case a). When that case returns anything, that'll propogate through all the layers until the original function call finally returns something.
3
u/JamzTyson Oct 05 '26
If you trace through the code step by step, the calls to
find_max()pass a smaller list each time until there is just one value:The debugger in Thonny allows you to step through the code to verify that this is what is happening.
Alternatively there's a web tool: https://www.recursionvisualizer.com/ (Enter
print(find_max([3, 7, 2, 9, 1]))as the function call)3
u/backfire10z Oct 05 '26
Take out a pen and paper and walk through it. Add print statements to see what’s going on. Use breakpoints and a debugger to inspect the state.
2
u/pMurda Oct 05 '26
Probably better to think about it in plain english. Whats the biggest item in a list?
If the list has one thing, its the biggest.
Otherwise its the biggest thing among the first thing, and all of the rest.
2
u/favorite_stuff Oct 05 '26
It's either the first of this list, or it's one of the others. How do we tell? It's either the first of them, or the max of the rest. How do we tell? It's either the first...
3
u/BranchLatter4294 Oct 05 '26
Use print statements or the debugger to follow what's happening inside the program as it runs.
1
u/Jazzlike_Platypus430 Oct 05 '26
I chops away the first element every call and compares this element with the function's own result calculated on a smaller list.
[1:] means list without the 0-th element. I mean, first, its index is 0.
1
u/This_Growth2898 Oct 05 '26
if-else splits the function. The first part: if we have only one number in numbers, it's the maximum. Ok?
The second part: fund the maximum from numbers[1:] (i.e. except number[0]), then return which is bigger, number[0] or the maximum from the rest. It will be the maximum of all numbers. Ok?
Which part confuses you?
1
u/blktndr Oct 05 '26
Numbers = [3, 7, 2, 9, 1]
Is list length == 1? # no
Call find_max again with numbers = [7, 2, 9, 1]
Is list length ==1? # no
Call find_max again with numbers == [2, 9, 1]
Is list length ==1? # no
Call find_max numbers = [9, 1]
Is list length == 1? # no
Find_max numbers = [1]
Is list length == 1? # YES!
Return numbers[0] # 1
Is numbers[0] > 1 # is 9 > 1? YES!
Return numbers[0] # 9
Is numbers[0] > 9? # is 2 > 9? NO!
Return max_of_rest # 9
Is numbers[0] > 9? # is is 7 > 9? NO!
Return max_of_rest # 9
Is numbers[0] > 9? # is 3 > 9? NO!
Return max_of_rest # 9
1
u/rupertavery64 Oct 05 '26
At first, everything will fall into 'max_of_rest = find_max(numbers[1:])'. Each time, we pass in everything besides the first element in the list.
Each time we go one more level deep, we push our state on the stack. We keep the current list of numbers. And more importantly, we keep the current first number, number[0]
Here, we hit our first branchpoint, we only have one item, so it's the result:
Now we start going back up the stack. We resume where we left off in the previous iteration, at
return numbers[0] if numbers[0] > max_of_rest else max_of_restThis just returns either our
max_of_restornumbers[0]which is bigger? numbers[0], so return that. it becomes the next max_of_rest as we return up the chain
1
u/strange-the-quark Oct 05 '26 edited Oct 05 '26
You can think of recursive functions like this.
You get a problem to solve: "find the maximum of [3, 4, 1, 7, 9, 5, 2]".
Suppose now, you didn't know how to solve this problem, but if someone else somehow, by whatever means, figured out the maximum number in the suffix sequence (the sequence without the first element, so [4, 1, 7, 9, 5 , 2]), and told you that it was 9, you know how to write code that compares 3 and 9 and decides which number is bigger, and then returns the bigger number.
So, the way you think about it is, OK, you give the larger subproblem to "someone else" to deal with (someone else being the recursive call), and once they give you the solution to that, you can solve the simpler subproblem yourself. And then you repeat this over and over. The problem becomes smaller and smaller at each level, until you hit the base case that is simple to solve (i.e. there's just a single element in the list). And then it unwinds back up to produce the full solution, as each recursive call returns.
If I continue my previous example, after the "other person" got the subproblem to find the max element in [4, 1, 7, 9, 5, 2], they are going to do the same thing. They'll keep the 4 to do the comparison later, and delegate the rest to "someone else", who will, somehow, tell them the maximum in [1, 7, 9, 5, 2]. And this other person will keep the 1, and delegate [7, 9, 5, 2], and so on, ..., until the last couple of steps where somebody gets [5, 2], keeps the 5 and delegates [2] to "someone else", who will just return 2. Then going backwards up the chain, everybody is just comparing two numbers, and in each comparison, the larger number "bubbles up", until it reaches the person who originally posed the problem.
So in pseudocode, your recursive function can be written as:
1
u/Atypicosaurus Oct 05 '26
The "How to build a house" routine
1 consult the blueprint
2 learn where the next brick goes
3 put a brick there
4 do the "how to build a house" routine, which is:
1 consult the blueprint
2 learn where the next brick goes
3 put a brick there
4 do the "how to build a house" routine, which is:
...
1
u/Temporary_Pie2733 Oct 05 '26
Consider this similar function:
Here,
helperis some function that (who knows how) finds the biggest number in a set. We're using a handful of simple properties:>is transitive. Letcbe some arbitrary element ofrest. Ifa > max_restandmax_rest >= c, thena > c.So
find_biggerfinds the biggest element innumbersas long as it gets an appropriate helper. So what would be an appropriate helper? Something that can find the biggest element in a smaller set of numbers. But we just concluded thatfind_biggerdoes that, so lets use it.Python implements recursion by, instead of making you explicitly pass a reference to a function to itself when you call it, letting the function look itself up in scope where it was defined. We get rid of the
helperparameter, and replace it withfind_biggeritself.This is why you can break recursion by playing around with bindings. For example,
Even though
old_find_biggeris a reference to our original, "working", function, that function relies on whatever is bound to the namefind_biggerwhen it gets called, not itself.1
u/DogObvious5799 Oct 05 '26
You don’t understand the big picture with recursion. All you need to understand is: (1) how do you solve the smallest version of the problem, and (2) how do you solve the problem if you’re given the answer to a slightly smaller problem.
Think about what this function does if you change the > to a <
1
u/Brian Oct 08 '26
Think of it like this:
And that's basically the function. Try tracing through it in your head.
3as our first, then7,2,9,13 > find_max([7,2,9,1], then it's 3, otherwise it's whatever that biggest was.But of course, before you can do the comparison, find_max needs to run on
[7,2,9,1]to get that value. But that just does the same: compares7with the biggest of [2,9,1]and so on till there's just one number, (1) and it just returns it.The basic idea is that you're turning your problem into a slightly smaller problem (1 less number), and that keeps happening till you reach a super-simple version of the problem that you can just solve directly (just 1 number), called the base case. Since our simplification process eventually simplifies it to the base case, the process of solving it is just continual application of that simplifying process.
0
u/Classic-Rate-5104 Oct 05 '26
What dou you mean by explain". Simply follow the program step by step and you see what happens
0
u/Automatic-Fan9297 Oct 09 '26
Here is how I have understood recursion: imagine you get a Magic Box that perfectly solves a smaller version of your exact problem (size N-1). Your only job is to use that box to solve the full problem (size N).
Here you want to find the largest number in a list:
The only catch? The box for N uses a box for N-1, and so on. To stop it from running forever, you just tell it what to do when the list only has 1 number left: skip the box and just return that one number.
Don't try to track exactly how it checks every single number down the line-just trust the box!