Почему элемент в стеке не удаляется сразу же после возвращения в рекурсии?

Question

Хорошо, это может быть глупый вопрос. Но я думал, что всякий раз, когда вы что-то возвращаете, элемент в стеке отрывается. Но в случае рекурсии элементы в стопке продолжают накапливаться, пока не достигнут базового варианта. Тогда это начинает всплывать. Мне было интересно, почему это так.

А также, когда именно элемент попадает из стека?

Спасибо

Answer 1

Я собираюсь предположить, что под "элементом" вы ссылаетесь на кадр стека функции стек вызовов , а не на элемент элемента в структуре данных стека (который работает как стек вызовов). Я надеюсь прояснить вопрос о том, как работает стек вызовов.

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

---

Рекурсивная функция - это функция, которая вызывает сама себя. Всякий раз, когда вызывается функция, поток, достигший инструкции вызова функции, создает кадр стека. Кадр стека - это фрагмент памяти, содержащий все данные, необходимые для выполнения вызываемой функции (переменные, параметры и т. Д.). Этот кадр «помещается» на вершину стека вызовов. Выполняемая в данный момент функция, которая выполняет вызов, временно приостанавливается, и указатель стека перемещается вверх в новый кадр, который затем выполняется.

Без базового случая или условного состояния, когда функция больше не выполняет рекурсивные вызовы, рекурсия будет продолжаться бесконечно. Когда это происходит, операционная система посылает сигнал для завершения процесса, когда он превышает использование стека (обычно что-то около 1 МБ).

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

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

Вот пример программы на C и Python, содержащей рекурсивную функцию и диаграмму:

#include <stdio.h>

void count_to(int n) {
    if (n > 0) {
        count_to(n - 1);
    }

    printf("%d\n", n);
}

int main() {
    count_to(4);
    return 0;
}

def count_to(n):
    if n > 0:
        count_to(n - 1)

    print(n)

count_to(4)

Вот вывод программы:

0
1
2
3
4

Вот как выглядит стек вызовов во время выполнения:

[count_to(4)]  <-- top of call stack/stack pointer
[main]         <-- bottom of call stack

[count_to(3)]  <-- 
[count_to(4)]  
[main]         

[count_to(3)]  <--
[count_to(4)]
[main]         

[count_to(2)]  <-- 
[count_to(3)]
[count_to(4)]
[main]         

[count_to(1)]  <--
[count_to(2)]
[count_to(3)]
[count_to(4)]
[main]         

[count_to(0)]  <--
[count_to(1)]
[count_to(2)]
[count_to(3)]
[count_to(4)]
[main]         

На данный момент еще ничего не напечатано. Поток только что добавил вызовы функций в стек. Но как только мы вызываем count_to(0), рекурсия прекращается. Когда мы извлекаем кадры из стека, каждая функция напечатает свое локальное значение n и вернется к своему вызывающему.

print(0)
return

[count_to(1)]  <-- 
[count_to(2)]
[count_to(3)]
[count_to(4)]
[main]         

print(1)
return

[count_to(2)]  <-- 
[count_to(3)]
[count_to(4)]
[main]         

print(2)
return

[count_to(3)]  <--
[count_to(4)]
[main]         

print(3)
return

[count_to(4)]  <--
[main]         

print(4)
return

[main]         <--

Наконец, выполнение возвращается к основному, который выходит.

---

Я рекомендую прочитать статьи Википедии, такие как выделение памяти на основе стека и стек вызовов и написать множество миниатюрных рекурсивных программ, подобных приведенному здесь примеру, чтобы увидеть, как они работают.

Answer 2

Например:

def bar(n):
    if n > 0:
        print(n)
        return bar(n-1)
    return 'end'

в операторе return bar(n-1), мы сначала выполняем bar(n-1), а затем возвращаем the return value из bar(n-1).

Когда мы выполним bar(n-1), мы встретимся в одинаковом случае, если n > 0 больше не будет True.

Именно поэтому мы можем иметь рекурсию.

Может бытьмое объяснение скучно, я хочу поделиться с вами визуализированной ссылкой , , которую вы действительно хотите посмотреть .