с пониманием этого кода

Question

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

def depth(L) : 
    nesting = [] 
    for c in L: 
     if type(c) == type(nesting) : 
      nesting.append(depth(c)) 
    if len(nesting) > 0: 
     return 1 + max(nesting) 
    return 1 

Поэтому, естественно, я начинаю путаться в соответствии с Append, который вызывает рекурсию. Кто-нибудь имеет простой способ объяснить, что здесь происходит? Я не уверен, что на самом деле добавляется, и проходить через него с помощью тестовых случаев в моей голове не помогает. Благодаря!

изменение: извините, если форматирование бедно, я напечатал это от моего телефона

Answer 1

Позвольте мне показать вам простой способ, изменить код так: (### являются новые строки, я добавил в свой код, чтобы вы могли посмотреть, что там происходит)

def depth(L) : 
    nesting = [] 
    for c in L: 
     if type(c) == type(nesting) : 
      print 'nesting before append', nesting ###  
      nesting.append(depth(c)) 
      print 'nesting after append', nesting ### 
    if len(nesting) > 0: 
     return 1 + max(nesting) 
    return 1 

Теперь давайте составить список с глубиной 3:

l=[[1,2,3],[1,2,[4]],'asdfg'] 

Вы можете увидеть наш список из 3 элементов. один из них - это список, другой - список, в котором есть другой список, а последний - строка. Вы можете ясно видеть глубину этого списка 3 (то есть 2 списка вложенных вместе во втором элементе основного списка)

Позволяет запустить этот код:

>>> depth(l) 
nesting before append [] 
nesting after append [1] 
nesting before append [1] 
nesting before append [] 
nesting after append [1] 
nesting after append [1, 2] 
3 

Кусок торта! эта функция добавляет 1 к вложенности. то, если в элементе есть еще один список, он добавляет 1 + максимальное число в гнездовании, которое называется числом времени. и если элемент является строкой, он пропускает его.

В конце он возвращает максимальное число в гнездовании, которое является максимальным числом повторений рекурсии, которое является числом времени, когда в главном списке есть список внутри списка, а также глубина. В нашем случае рекурсия произошла дважды для второго элемента + 1 = 3, как мы и ожидали.

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

Answer 2

Так что это, кажется, это функция, которая принимает список и вычисляет, как вы выразились, то глубина вложенности него. nesting - это список, поэтому то, что говорит if type(c) == type(nesting): если элемент в списке L - это список, снова запустите функцию и добавьте ее, а когда она снова запустит эту функцию, она выполнит тот же тест, пока не появится больше вложенных списков в списке L, а затем возвращает 1 + максимальное количество вложенных списков, поскольку каждый список имеет глубину 1.

Пожалуйста, скажите мне, если какая-либо из этого неясно

Answer 3

этого алгоритма посещения вложенных списков и добавляет один для каждый уровень рекурсии. Цепь вызова, как это:

depth([1, 2, [3, [4, 5], 6], 7]) = 
    1 + depth([3, [4, 5], 6]) = 3 
     1 + depth([4, 5]) = 2 
      1 

Так как глубина ([4,5]) никогда не входит в состояние if type(c) == type(nesting) потому, что ни один из элементов не является списком, он возвращает 1 от внешнего возврата, который является базовым сценарием.

В случае, если для заданной глубины имеется более одного вложенного списка, например. [1, [2, 3], [4, [5, 6]], максимальная глубина [2,3] и [4, [5, 6]] прилагаются к вызову глубины, из которых max возвращается внутренним возвратом.

Answer 4

Начнем с нескольких примеров.

Прежде всего, рассмотрим список с одним уровнем глубины. Например, [1, 2, 3].

В вышеуказанном списке кода начинается с вызова depth() с кодом L = [1, 2, 3]. Он делает пустой список nesting. Итерации по всем элементам L i.e 1, 2, 3 и не находит ни одного элемента, который проходит тест type(c) == type(nesting). Проверка, что len(nesting) > 0 сбой, и код возвращает 1, что является глубиной списка.

Далее, давайте возьмем пример с глубиной 2, т.е. [[1, 2], 3]. Функция depth() вызывается с L = [[1, 2], 3] и создается пустой список nesting. Цикл итерации над 2 элементами L i.e [1, 2] , 3 и с type([1, 2]) == type(nesting), nesting.append(depth(c)). Как и в предыдущем примере, depth(c) i.e depth([1, 2]) возвращает 1 и nesting теперь становится [1]. После выполнения цикла код оценивает тест len(nesting) > 0, который приводит к True и 1 + max(nesting), который возвращается 1 + 1 = 2.

Аналогично, код следует за глубиной 3 и так далее.

Надеюсь, это было полезно.