Несколько рекурсивных вызовов

Question

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

float foo(int n){ 

    int a = 0; 
    for(int i = 0; i < n; i++) 
     a += 1; 

    if (n > 2) 
     return foo(n/2) + foo(n/2); // What happens here? 

    return a; 
} 

Должен ли я думать о двух разных стеков сейчас или то, что это лучший способ, чтобы представить себе результат?

Answer 1

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

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

Answer 2

return foo(n/2) + foo(n/2); // What happens here? 

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

Это помогает визуализировать его?

Answer 3

Должен ли я думать о двух разных стеках сейчас или о том, что является лучшим способом для визуализировать результат?

Это еще один стек. В этой строке:

return foo(n/2) + foo(n/2); // What happens here? 

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

Answer 4

Давайте попробуем представить себе стек (да, есть только один стек) для различных этапов обув вызова (4):

перед вызовом Foo (4): абоненте стек

в пределах первоначального вызова Foo (4): стек = абонент-стек, Foo (4)

, когда Foo (4) находится в пределах первого вызова Foo (2): абоненте-стек, Foo (4), foo (2)

foo (4) в первом вызове foo (2), где foo (2) уже вызвал первый foo (1): caller-stack, foo (4), foo (2), foo (1)

после возвращения из первого Foo (1): снова абонент-стека, Foo (4), Foo (2)

Foo (4) в пределах первого вызова Foo (2), где foo (2) вызвал второй foo (1): caller-stack, foo (4), foo (2), foo (1)

после возвращения из второго foo (1) : Снова абонент-стека, Foo (4), Foo (2)

после возвращения из первого Foo (2): абоненте-стек, Foo (4)

Foo (4) находится в пределах второй вызов Foo (2): абонент-стек, Foo (4), Foo (2)

Foo (4) в пределах второго вызова Foo (2), где Foo (2) уже называется первый foo (1): caller-stack, foo (4), foo (2), foo (1)

после возвращения из первого Foo (1): снова абонент-стека, Foo (4), Foo (2)

Foo (4) в пределах второго вызова Foo (2), где Foo (2) имеет называется второй Foo (1): абонент-стека, Foo (4), Foo (2), Foo (1)

после возвращения из второго Foo (1): снова абонент-стека, Foo (4) , Foo (2)

после возвращения из второго Foo (2): абонент-стек, Foo (4)

после возвращения из Foo (4): вызывающих стек