Понимание прохождения рекурсивного кода - PullRequest
Новая
       24

Понимание прохождения рекурсивного кода

0 голосов
/ 19 июня 2020
• 1000 в строку, где была вызвана функция.

Теперь, когда дело доходит до рекурсии, когда я продолжаю вызывать ту же функцию, как ведет себя рука? Есть ли новая рука для каждого вызова функции? Я не понимаю, как код «возвращается вверх по дереву рекурсивных вызовов». Я так понимаю есть стек. Я видел все эти видео, объясняющие это.

Чего я не понимаю, так это того, что если я напишу операторы cout, один выше и один под рекурсивным вызовом, тогда я пойму, почему выполняется оператор cout над рекурсивным вызовом столько раз, сколько вызывается рекурсивная функция, но тогда как оператор cout под рекурсивным вызовом также выполняется столько раз? Вот пример 
int Factorial(int n)
{
  cout<<"first cout statement before the recursive call";
  if( n == 0 )
     return 1;
  int F = n*Factorial(n-1);
  cout<<"second cout statement after the recursive call";
  return F; 
}
int main()
{
 int n;
 cin>>n;
 int result = Factorial(n);
 cout<<result;
}

Это результат ниже. 

first cout statement before the recursive call
first cout statement before the recursive call
first cout statement before the recursive call
first cout statement before the recursive call
first cout statement before the recursive call
first cout statement before the recursive call

second cout statement after the recursive call  //Notice these
second cout statement after the recursive call
second cout statement after the recursive call
second cout statement after the recursive call
second cout statement after the recursive call
120

1 Ответ

2 голосов
/ 19 июня 2020

Думайте о стеке вызовов как о подносе учетных карточек. Стек начинается пустым. Единственное, что вы можете сделать, это записать новую учетную карточку и положить ее сверху или снять то, что находится сверху.

В этот лоток есть кое-что, помещенное средой выполнения, но для А сейчас давайте представим, что лоток пуст, когда main() начинает работать.

Представьте, что каждая функция - это глава в книге. На каждой странице есть набор отдельных предложений, каждое из которых говорит вам сделать одно конкретное c действие. Одна из таких вещей может быть: «go перейти в другую главу и делать то, что в ней сказано, используя эту информацию, которая у меня есть». Когда вы дойдете до такого предложения, вам нужно будет вспомнить, как вернуться туда, где вы были, поэтому вы запишите следующее на карточке:

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

Вы кладете эту карточку на верхнюю часть лотка, затем переходите к другой главе и начинаете что-то делать. с этой главой, go назад к последней главе с таким результатом "затем вы снимаете карточку с верха, возвращаетесь к той главе, в которой она написана, находите предложение, следующее сразу за тем, которое указывает карточка, и продолжаете оттуда .

Вот и все, что здесь происходит. Главы - это функции. Предложения - это машинные инструкции. Все, что вы перенесете в другую главу, - это аргументы функций. Возвращаемое значение - это то, что вы берете из главы. «Материал, с которым вы работали», который вы записываете в учетную карточку, - это значение любых локальных переменных функции во время вызова функции.

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

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

Итак, в вашем случае, да, вы могли подумать об этом что у вас «несколько рук». Как бы глубоко вы ни рекурсивно переходили в одну и ту же функцию, вам придется продвигаться вверх по мере возврата каждого рекурсивного вызова.

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

...