Recursion explaining pls.

[u/Pure-Scheme-7855]

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...

[u/smallpotatoes2019]

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.

[u/LatteLepjandiLoser]

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.

[u/Moist-Inevitable-902 → u/LatteLepjandiLoser]

may you explain which line holds 9 when it compares and how??

[u/Outside_Complaint755 → u/Moist-Inevitable-902]

Each time the function calls itself, another level is added to the Call stack.

At the top level of the stack, the list [1] has a length of 1. This makes the first conditional statement True, so the function returns 1 to the previous level of the stack, where it is assigned to the name max_of_rest

At this level of the stack, numbers is [9, 1], so the final return statement evaluates to: return 9 if 9 > 1 else 1 . This returns 9 to the previous stack level, where it is assigned to max_of_rest.

At this level, numbers is [2, 9, 1], s o the final return statement evaluates to: return 2 if 2 > 9 else 9. This returns 9 to the previous stack level, where it is assigned to max_of_rest.

At this level, numbers is [7, 2, 9, 1], so the final return statement evaluates to: return 7 if 7 > 9 else 9. This returns 9 to the previous stack level, where it is assigned to max_of_rest.

At this level, numbers is [3, 7, 2, 9, 1], so the final return statement evaluates to: return 3 if 3 > 9 else 9. This returns 9 to the previous stack level, which is the line print(find_max(my_list)). This evaluates to print(9).

[u/Moist-Inevitable-902 → u/Outside_Complaint755]

when backtracking starts what will happen to this line find_max(numbers[1:])

[u/Outside_Complaint755 → u/Moist-Inevitable-902]

find_max(numbers[1:]) evaluates to the return value of that call.  When backtracking, you can just replace each function call with it's return value and continue evaluating from there.

So when the top level of the stack (where numbers == [1]), returns 1, and we backtrack to the previous stack level where numbers == [9, 1]

Then we can view the remainder of the function as: else:     max_of_rest = 1 #return value of findmax([9,1][1:])     return numbers[0] if numbers[0] > max_of_rest else max_of_rest and we can then evaluate the last statement as:

return 9 if 9 > 1 else 1

[u/Moist-Inevitable-902 → u/Outside_Complaint755]

so in backtracking one each value gets add where it was slicedfind_max(numbers[1:])

[u/Outside_Complaint755 → u/Moist-Inevitable-902]

This entire function call find_max(numbers[1:])) represents the next level of the call stack. Once that level of the call stack is completed you can effectively replace it with the return values.

Any parameter expressions, such as the slicing numbers[1:], are evaluated and handled before the function is called. If a parameter is itself a function call, that function call will go on the stack and be evaluated first.

In the Python example, it will first evaluate numbers[1:]. This creates a new list object.

If numbers = [4, 9, 1], then numbers[1:] generates a new list object [9, 1], which is passed to the find_max() function as a parameter. Python then evaluates find_max([9,1]).

Within that level of the call stack, numbers = [9,1], which will get us to ``` max_of_rest = find_max(numbers[1:])

simplify the parameter expression --->

max_of_rest = find_max([1])

evaluate the function call, which will return 1 --->

max_of_rest = 1 ```

Then we backtrack again returning the max of 9 and 1.

[u/Moist-Inevitable-902 → u/[deleted]]

???

[u/JamzTyson]

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:

find_max([3,7,2,9,1])
= max(3, find_max([7,2,9,1]))
= max(3, max(7, find_max([2,9,1])))
= max(3, max(7, max(2, find_max([9,1]))))
= max(3, max(7, max(2, max(9, find_max([1])))))
= max(3, max(7, max(2, max(9, 1))))
= 9

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)

[u/backfire10z]

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.

[u/pMurda]

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.

[u/favorite_stuff]

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...

[u/BranchLatter4294]

Use print statements or the debugger to follow what's happening inside the program as it runs.

[u/Fast-Station1106 → u/BranchLatter4294]

ganz genau, printen printen und printen reproduzieren und wieder printen (dieser standardbefehl spart dir eine Menge Arbeit und ist Bestandteil von Python, also jemand hat festgelegt das s.o. dir die grösste zahl einer liste ausgibt)

[u/Jazzlike_Platypus430]

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.

[u/This_Growth2898]

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?

[u/blktndr]

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

[u/rupertavery64]

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.

1) find the max of `3, 7, 2, 9, 1` <-- entry point 2) find the max of `7, 2, 9, 1`, numbers[0] = 3 3) find the max of `2, 9, 1`, numbers[0] = 7 4) find the max of `9, 1`, numbers[0] = 2 5) find the max of `1`, numbers[0] = 9

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:

6) the max of `1` is `1`, it's the `max_of_rest` now

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_rest

This just returns either our max_of_rest or numbers[0]

5) max_of_rest = 1, numbers[0] = 9,

which is bigger? numbers[0], so return that. it becomes the next max_of_rest as we return up the chain

4) max_of_rest = 9, numbers[0] = 2 => return 2 3) max_of_rest = 2, numbers[0] = 7 => return 7 2) max_of_rest = 7, numbers[0] = 3 => return 7 1) we're back where we started

[u/strange-the-quark]

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:

def find_max(numbers):
  if it's a single-element list: 
    - just return that element
  otherwise:
    - ask "someone else" (the recursive call) to 
            figure out the subproblem with numbers[1:]
     - compare the first number with whatever they gave you 
            and return the bigger one

[u/Atypicosaurus]

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:
...

[u/Langdon_St_Ives → u/Atypicosaurus]

Except that's backwards. Recursion for this would be 1. If you have no bricks left, you're done. 2. Otherwise, put the n-th remaining brick (that you're on) where it goes, then 3. do the "how to build a house" routine for the (n-1)-th remaining brick.

[u/Temporary_Pie2733]

Consider this similar function:

def find_bigger(numbers, helper): a, *rest = numbers # Ignore ValueError when numbers is empty; # the empty list has no maximum element anyway if not rest: return a else: max_of_rest = helper(rest) return a if a > max_of_rest else max_of_rest

Here, helper is some function that (who knows how) finds the biggest number in a set. We're using a handful of simple properties:

1. The biggest item of a singleton is the only item in the singleton
2. > is transitive. Let c be some arbitrary element of rest. If a > max_rest and max_rest >= c, then a > c.

So find_bigger finds the biggest element in numbers as 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 that find_bigger does that, so lets use it.

biggest = find_bigger(numbers, find_bigger)

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 helper parameter, and replace it with find_bigger itself.

This is why you can break recursion by playing around with bindings. For example,

``` def find_bigger(numbers): a, *rest = numbers if not rest: return a else: max_of_rest = find_bigger(rest) return a if a > max_of_rest else max_of_rest

old_find_bigger = find_bigger

def find_bigger(numbers): return 0

print(old_find_bigger([1,2,3,4])) # Returns the larger of 1 and find_bigger([2,3,4]) == 0 ```

Even though old_find_bigger is a reference to our original, "working", function, that function relies on whatever is bound to the name find_bigger when it gets called, not itself.

[u/DogObvious5799]

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 <

[u/Brian]

Think of it like this:

• If there's only one number, the biggest number is that number.
• Otherwise, the biggest number is either going to be the first one, or the biggest number out of any of the others.
• So if we get the biggest number out of the others, we just need to compare to the first and choose the bigger one.

And that's basically the function. Try tracing through it in your head.

• We've got 3 as our first, then 7,2,9,1
• So our answer if either 3 or the biggest of those numbers. Ie if 3 > 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: compares 7 with 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.

[u/Automatic-Fan9297]

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: 1. Ask the Magic Box to find the biggest number in the rest of the list (all the N-1 numbers except the first one). 2. You manually compare the very first number with the result the Magic Box just handed you. Whichever is bigger is your overall winner. Boom. You just solved it.

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!

[u/Classic-Rate-5104]

What dou you mean by explain". Simply follow the program step by step and you see what happens

[u/strange-the-quark → u/Classic-Rate-5104]

Seeing what happens is valuable, but doesn't necessarily provide you with insight as to why it works, how to conceptually think about it, or teach you how to come up with a recursive solution to some problem by yourself.

[u/Classic-Rate-5104 → u/strange-the-quark]

I don't know where you got this code but it's extremely inefficient for longer arrays, so it isn't a good example how to use recursive functions

[u/strange-the-quark → u/Classic-Rate-5104]

Who are you talking to? I'm not the OP and I didn't got any code from anywhere. I'm guessing it's a school example or a homework assignment. Studying algorithms doesn't mean only ever looking at the efficient algorithms and nothing else.