Фото: Мартин Адамс on Unsplash
Рассмотрим приведенный ниже фрагмент кода, который имеет две функции foo и main. Специальная переменная __name__ , которая в основном задается интерпретатором python перед выполнением, и ее значение устанавливается в __main__ при выполнении в качестве основной программы.
В python, если функция не заканчивается оператором return или имеет оператор return без какого-либо выражения, возвращается специальное значение None.
#!/usr/bin/python
def foo(msg):
print '{} foo'.format(msg)
def main():
msg = 'hello'
foo(msg)
if __name__ == '__main__':
main()
# end
Чтобы определить выходные данные приведенного выше кода, нам нужно знать, в каком порядке Python выполняет строки кода. Мы можем запустить его и получить результат, но дело не в этом.
Интерпретатор Python выполняет код с отступом уровня 0. В приведенном выше случае метод main() будет выполняться как его отступ на уровне 0. Это начальная точка выполнения программы, и ход выполнения сохраняется в стеке времени выполнения.
Что такое стек времени выполнения?
Это простой стек времени выполнения, в котором кадры вызова добавляются в стек, и они выскакивают один за другим, пока он не достигнет последнего кадра в стеке, а затем выполнение завершается.
Это стек времени выполнения для нашего простого примера программы.
Каждый блок в стеке называется кадром вызова, он же записи активации. Они хранятся в памяти, чтобы отслеживать выполнение вызова функции, и выделенная память освобождается при возврате функции.
Фрейм вызова добавляется поверх стека при вызове функции и удаляется при возврате функции. Он содержит имя функции, которая была вызвана, и место, откуда ее можно забрать(номер строки) при возврате функции.
Параметры и локальные переменные, определенные внутри функции, также помещаются в стек и выскакивают при возврате функции.При вызове функции с параметрами параметры становятся локальной переменной в стеке, которая инициализируется фактическим значением параметра.
Таким образом, даже если две функции имеют одинаковое имя локальной переменной, они отличаются, поскольку они по-разному отображаются в стеке. Один и тот же вызов функции из разных мест может иметь разное значение для одних и тех же переменных. Понимание этой концепции важно для понимания того, как работает рекурсия.
Ниже приведена простая программа для добавления чисел из списка с помощью рекурсии.
#!/usr/bin/python
def sum_list(l):
if not l:
return 0
return l[0] + sum_list(l[1:])
def main(l):
total = sum_list(l)
print total
if __name__ == '__main__':
main([1, 2, 3])
# end
Ниже приведена трассировка стека вышеприведенной программы для рекурсивного получения суммы чисел в списке.
Понимание рекурсии под капотом может помочь нам увидеть ее рабочий механизм, который не является магией. А для написания рекурсивной функции требовался базовый случай, чтобы определить, когда завершать. Без базового случая он застрянет в цикле и завершится ошибкой.