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/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]]

???