CODEWITHSUNDEEP
pythonlistrecursion
mdvenkatesh nuhk
mdvenkatesh nuhk

Reputation: 125

recursion working in python code to find max

I am new to the concept of recursion trying to figure how the following code is working

def Max(list):
    if len(list) == 1:
        return list[0]
    else:
        m = Max(list[1:])
        return m if m > list[0] else list[0]

def main():
    list = eval(raw_input(" please enter a list of numbers: "))
    print("the largest number is: ", Max(list))


    main()

I am having the following doubts while looking at the code

1) How the slicing is working here without giving the slice where it should end [0:9](in these manner how the list is being sliced)

2)When will the **return m if m > list[0] else list[0]**statement will be called (i am thinking it won't be called because before return we will be calling the function several times )

Upvotes: 3

Views: 101

Answers (2)

Maurice
Maurice

Reputation: 13108

Welcome to recursion - it's difficult to understand, but it has a strange kind of elegance/beauty to it.

It usually helps me to think about this with an example.

Let's assume this list: 1, 2, 3

We're going to run Max([1,2,3])

  1. The length of the list is 3, so we jump to the else-part
  2. We run Max([2,3]) and save the result to m (Recursion #1)
    1. The length of [2,3] is != 0, we go to else
    2. We run Max([3]) and save the result to m (Recursion #2)
      1. The length of [3] is == 1
      2. We return index 0, which is 3 (End of Recursion #2)
    3. We get a value of 3 for m
    4. Now we get to the statement return m if m > list[0] else list[0]
    5. Recap: m = 3 and list=[2,3]
    6. m > list[0] so we return m=3 (End of Recursion #1)
  3. Recap time again: m=3 and list=[1,2,3]
  4. m > list[0] so we return m=3

The result of Max([1,2,3]) is 3.

Note that each call to Max in the code creates "new" variables for m and list that are only visible inside of that function. The inner Max doesn't know about m and list of the outer Max and vice versa.

The calls flow looks like this:

+----------------+
|   Max([1,2,3]  | +----+
+------^---------+      | Step 1
       |                |
Step 4 |       +--------v------+
       +-------+   Max([2,3])  +---+
   return 3    +---^-----------+   | Step 2
                   |               |
           Step 3  |     +---------v-----+
                   +-----+   Max([3])    |
             return 3    +---------------+

To address 1):

When we slice using [n:] this means: start at index n and take the rest of the list.

To address 2):

After we get out of the recursion, see the example above.

Further Reading

Edit in response to your comment

To help you understand the line return m if m > list[0] else list[0] I suggest you try to mentally keep track of the state before the recursive call and after the recursive call.

The idea of this Max implementation is this: Recursively go to the last element in the list, then take that and check it against the second-to-last element if the last is larger keep that, otherwise keep the second-to-last.

If your list looked like this [1,6,3,5,4,2], the levels of recursion would return this:

The first number in the bracket is m and the second is the value of list[0]

  • 2 (N/A, 2)
  • 4 (2, 4)
  • 5 (4, 5)
  • 5 (5, 3)
  • 6 (5, 6)
  • 6 (6, 1)

Ultimately the function begins at the end of the list, takes the last value as the initial value and moving to the beginning, while always keeping the larger value which results in the largest value being returned.

(This is difficult to put into writing, hopefully you'll understand)

Upvotes: 2

Prodiction
Prodiction

Reputation: 187

  1. This is a normal way of slicing. [1:] means from the first element until the end.
  2. The function is recursive. So if you have a list of elements [4,3], it

1) takes the else branch of the if statement two times, computes [4,3][1:] as [3] and calls Max([3])).

2) The list in the second stage of the recursion has length of 1, so it takes the first branch of the if-statement and returns 3 as elements.

3) we are back in the first call, where we compare the first element list[0]=4 with the result m=3 and get the bigger of them as return value.

Upvotes: 0

Related Questions