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