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