В Python Как работает рекурсия во время выполнения

фото Мартин Адамс на Скрыть

Рассмотрим приведенный ниже фрагмент кода, в котором есть две функции foo и main. Специальная переменная __name__ который в основном устанавливается интерпретатором python перед выполнением, и его значение устанавливается равным __main__ при выполнении в качестве основной программы.

В python, если функция не заканчивается оператором возврата или имеет оператор возврата без какого-либо выражения, возвращается специальное значение None.

def foo(msg):
    print '{} foo'.format(msg)

def main():
    msg = 'hello'
    foo(msg)

if __name__ == '__main__':
    main()

Чтобы определить вывод приведенного выше кода, нам нужно знать, в каком порядке Python выполняет строки кода. Мы можем запустить его и получить результат, но это не главное.

Интерпретатор Python выполняет код с отступа уровня 0. В приведенном выше случае метод main() будет выполняться с отступом на уровне 0. Это начальная точка выполнения программы, а ход выполнения хранится в стеке времени выполнения.

Что такое стек времени выполнения?

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

Это стек времени выполнения для нашей простой примерной программы.

Каждый блок в стеке называется кадром вызова, также известным как записи активации. Они хранятся в памяти для отслеживания выполнения вызова функции, а выделенная память освобождается при возврате функции.

Фрейм вызова добавляется поверх стека при вызове функции и удаляется при выходе из функции. Он содержит имя вызванной функции и место ее получения (номер строки) при возврате функции.

Параметры и локальные переменные, определенные внутри функции, также помещаются в стек и извлекаются при выходе из функции. При вызове функции с параметрами параметры становятся локальными переменными в стеке, которые инициализируются фактическим значением параметра.

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

Ниже приведена простая программа для добавления чисел из списка с использованием рекурсии.

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

Ниже приведена трассировка стека вышеуказанной программы для рекурсивного получения суммы чисел в списке.

Понимание рекурсии под капотом может помочь нам увидеть ее рабочий механизм, который не является магией. И для написания рекурсивной функции требовался базовый случай, чтобы определить, когда завершить. Без базового случая он застрянет в цикле и завершится с ошибкой.