Блог

Поэтому я только что решил проблему с кодом на AlgoExpert, и я пытался получить более глубокое понимание того, почему мой код работает, поэтому я использовал PythonTutor для визуализации выполнения кода, и мне любопытно узнать, почему каждый раз, когда выполняется рекурсивный вызов, arraySum повторно инициализируется до 0, но каким-то образом сохраняет значение, которое было ранее, которое состояло из суммы элементов в массиве.

Вот проблема, которую я решил

Вот мой код:

 function productSum(array, multiplier=1) {
    let arraySum = 0;
    array.forEach(el => Array.isArray(el) ? arraySum =productSum(el, multiplier 1) : arraySum  = el)
    return arraySum * multiplier
}

productSum([5, 2, [7, -1], 3, [6, [-13, 8], 4]])
 

Вот ссылка на визуализацию в Array.isArray(el) ? arraySum+=productSum(el, multiplier+1) : arraySum += el)
return arraySum * multiplier
}

productSum([5, 2, [7, -1], 3, [6, [-13, 8], 4]])amp;cumulative=falseamp;heapPrimitives=nevernestamp;mode=editamp;origin=opt-frontend.jsamp;py=jsamp;rawInputLstJSON=[]amp;textReferences=false» rel=»nofollow noreferrer»>PythonTutor

Это становится ясно, когда вы понимаете, что каждое выполнение productSum имеет свою собственную arraySum переменную. Хотя имя каждый раз одно и то же, на самом деле это переменная, которая не связана с другими переменными (в дереве рекурсии), которые имеют одно и то же имя.

Каждый раз, когда выполняется рекурсивный вызов, вызывающий productSum объект попадает в кадр стека, откуда он восстанавливается при возврате рекурсивного вызова, а затем возвращенное значение добавляется к его собственному productSum .

Таким образом, значение накапливается при выходе из рекурсии, и все эти различные productSum переменные, каждая из которых играет небольшую роль в получении промежуточного результата, пока он не будет возвращен вызывающему, который накапливал его дальше …и т. Д.

Ваш алгоритм содержит рекурсивный вызов: время productSum от времени вы снова вызываете себя с другими аргументами на более глубоком уровне в вашей структуре данных.

Каждый вызов получает свой собственный фрейм вызова со своей уникальной областью действия. Ваш let arraySum = 0 определен в функции (области), поэтому каждый вызов имеет свой собственный arraySum (инициализированный до 0), отдельно от других вызовов.

Я сделал еще одну диаграмму, где каждая коробка/овал-это рамка вызова:

Не отображалась часть умножения.

Каждый фрейм вызова имеет свою собственную область с собственными array multiplier arraySum переменными//. Каждый вызов начинается с arraySum = 0 , используется .forEach для добавления в эту переменную, а затем возвращает значение, сохраненное в переменной. Вот почему в визуализаторе Python вы видите arraySum , что время от времени становится 0. Дело не arraySum в том , что где-то становится реальным 0 , это потому, что вы смотрите на совершенно новый вызов функции сразу после let arraySum = 0 оператора.

Изменение arraySum в одной области не влияет на arraySum другую область, даже если обе области предназначены для одной и той же функции (но вызывают разные функции!).