CODEWITHSUNDEEP
pythonpython-3.xrecursion
KUJI BOI
KUJI BOI

Reputation: 33

Recursion How Does This Find The Max?

can someone explain how the line restMax = max(A[1:]) finds the max element in an array? I know it's breaking it down into subarrays each time, but how does this find the max?

def max(A):
     if len(A)==0 :
        return None
     if len(A)==1 :
        return A[0]
     restMax = max(A[1:])
     if A[0]>restMax :
        return A[0]
     return restMax

Upvotes: 1

Views: 59

Answers (1)

Ismael Padilla
Ismael Padilla

Reputation: 5566

Recursive functions can be tricky at first, so let's go through what this function does:

If max(A) is called on an empty array, it returns none.

if len(A)==0 :
    return None

If max(A) is called on an array with a single element, it returns that element:

if len(A)==1 :
    return A[0]

If max(A) is called on an array with more than one element, it does the following:

  • It splits A into two: the first element (the head, A[0]) and the other elements (the tail, A[1:]).
  • It finds out what the maximum of the tail is recursively (max(A[1:]), the tricky part).
  • If the head is bigger than the tail's max, it returns the head. Otherwise it returns the tail's max.

Putting it all together:

Let's go over what max([1,4,7,2]) looks like:

  • (1) [1,4,7,2] has several elements, so we split it in two: 1 and [4,7,2]. Let's find out what max([4,7,2]) is:

    • (2) [4,7,2] is split into 4 and [7,2]. Let's find out what max([7,2]) is.

      • (3) [7, 2] is split into 7 and [2]. Let's find out what max([2]) is.

        • (4) [2] has one element, so max([2]) returns 2.

      • Now we're back at (3). We compare 7 and max([2]) which returned 2. 7 is bigger, so max([7,2]) returns 7.

    • Now we're back at (2). We compare 4 and max([7,2]), which we've seen that returned 7. Since 7 is bigger that 4, we return 7.

  • Now we're back at (1). We had split our original array into 1 and [4,7,2]. max([4,7,2]) returned 7, so we compare 1 and 7. 7 is bigger, so max([1,4,7,2]) returns 7.

We're done! max([1,4,7,2]) is 7.

Upvotes: 3

Related Questions