рекурсия работает в коде Python, чтобы найти максимум

Question

Я новичок в концепции рекурсии, пытаюсь понять, как работает следующий код

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()

У меня возникают следующие сомнения при взгляде на код

1) Как срезы работают здесь без указания среза, где он должен заканчиваться [0: 9] (таким образом, как нарезается список)

2) Когда ** возвратит m, если m> list [0] else list [0] **, будет вызван оператор (я думаю, что он не будет вызван, потому что до возврата мы будем вызывать функцию несколько раз)

Answer 1

Добро пожаловать в рекурсию - ее трудно понять, но в ней есть странная элегантность / красота.

Обычно это помогает мне подумать об этом на примере.

Давайтепредположим, этот список: 1, 2, 3

Мы собираемся запустить Max([1,2,3])

1. Длина списка равна 3, поэтому мы перейдем к остальной части
2. Мы запускаем Max([2,3]) и сохраняем результат в m (Рекурсия # 1)
   1. Длина [2,3] равна! = 0, мы переходим к остальным
   2. Мы запускаемMax([3]) и сохраните результат в m (Рекурсия # 2)
      1. Длина [3] равна == 1
      2. Мы возвращаем индекс 0, который равен 3 (Конециз рекурсии № 2)
   3. Мы получаем значение 3 для m
   4. Теперь мы переходим к утверждению return m if m > list[0] else list[0]
   5. Резюмируем: m = 3 и list=[2,3]
   6. m > list[0], поэтому мы возвращаем m=3 (Конец рекурсии # 1)
3. Время повтора еще раз: m=3и list=[1,2,3]
4. m > list[0], поэтому мы возвращаем m=3

Результат Max([1,2,3]) is 3.

Обратите внимание, что каждый вызов Max в коде создает "новые" переменные для m и list, которые видны только внутриэта функция.Внутренний Max не знает о m и list внешнего Max и наоборот.

Поток вызовов выглядит следующим образом:

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

К адресу 1):

Когда мы срезаем, используя [n:], это означает:начните с индекса n и возьмите оставшуюся часть списка.

По адресу 2):

После того, как мы выберемся из рекурсии, см. пример выше.

---

Дополнительная литература

• Аналогия для преподавания рекурсии более на преподавателях CS

---

Изменить в ответ на ваш комментарий

Чтобы помочь вам понять строку return m if m > list[0] else list[0] Я предлагаю вам попытаться мысленно отслеживать состояние до рекурсивного вызова и после рекурсивного вызова.

Идея этой реализации Max заключается в следующем: рекурсивно перейти к последнему элементу в списке, затем взять его и проверить его по отношению ко второму-последнему элементу, если последний больше, сохраните это, в противном случае оставьте второй допрошлой.

Если ваш список выглядел следующим образом [1,6,3,5,4,2], уровни рекурсии вернули бы это:

Первое число в скобках - m, а второе - значение list[0]

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

В конечном итоге функция начинается в конце списка, принимает последнийзначение в качестве начального значения и перемещение в начало, при этом всегда сохраняя большее значение, что приводит к возвращению наибольшего значения.

(это трудно описать, надеюсь, вы поймете)

Answer 2

1. Это нормальный способ нарезки. [1:] означает от первого элемента до конца.
2. Функция рекурсивная. Так что если у вас есть список элементов [4,3], это

1) принимает ветвь else оператора if два раза, вычисляет [4,3][1:] как [3] и вызывает Max([3])).

2) Список на втором этапе рекурсии имеет длину 1, поэтому он принимает первую ветвь оператора if и возвращает 3 в качестве элементов.

3) мы вернулись к первому вызову, где сравниваем первый список элементов [0] = 4 с результатом m = 3 и получаем большее из них в качестве возвращаемого значения.