3

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 )

Improve this question

2 Answers 2

Reset to default
2

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)

Improve this answer
Sign up to request clarification or add additional context in comments.

9 Comments

Thanks for the great explanation and work , But how the list value is being stored (such as [2,3,] and 1,2,3 i am thinking code will get terminated once function call is finshed) do it create any memory space (if it creates any memory space when will it know to clear the memory space for example for much time will it store the list)
Each call to Max sort of creates new variables that are called m and list that exist within the scope of that call. So the "inner" Max doesn't know about the values of the "outer" Max and vice versa.
so finally i am thinking the result of the last execution passes the result to the last next execution in these manner the execution takes place(correct me if i am wrong)
Thanks a lot for patience and explanation
Not sure if understand your thought, but I tried to visualize it above. Think of it like opening one of those russian dolls and closing them.
|
0
  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.

Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.