C ++ Recursion Issue

Question

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

При попытке следовать примеру рекурсии на следующем веб-сайте http://www.cplusplus.com/doc/tutorial/functions2/, я столкнулся с дорожным ударом, который меня озадачил.

Я немного изменил код только для того, чтобы разобраться с кодом в примере рекурсии, и у меня довольно много мыслей вокруг него, но я не могу понять, почему переменная 'n' увеличивается в 'Pass B', когда Я не говорил программе увеличивать 'n'.

Не могли бы вы помочь объяснить это?

#include <stdlib.h>
#include <iostream>

using namespace std;

long factorial (long n)
{
  if (n > 1)
{
   long r(0);
   cout << "Pass A" << endl;
   cout << "n = " << n << endl;
   cout << "r = " << r << endl;

   r = n * factorial (n-1);

   cout << "Pass B" << endl;  
   cout << "n = " << n << endl;
   cout << "r = " << r << endl;
   return (r);
}
  else
   return (1);
}

int main ()
{
  long number;
  cout << "Please type a number: ";
  cin >> number;
  cout << number << "! = " << factorial (number) << endl;
  system ("pause");
  return 0;
}

Answer 1

Это потому, что вы unrolling рекурсия.

Вы на самом деле не увеличиваете n, вы просто возвращаетесь к предыдущему вызову функции, где n было n+1 до того, как вы вызвали factorial(n-1) ...

Когда вы начинаете, вы поднимаетесь на

   r = n * factorial (n-1);

, что вызовет другой вызов функции factorial.

Вы продолжаете делать это (начинайте с начала вашей функции и переходите к вызову factorial с n, уменьшенным на 1), пока в конечном итоге не вызовете вызов функции factorial, где n<=1.

В этом случае вы возвращаете 1, но вы возвращаетесь к предыдущему вызову факториала, где n было 2, вы выполняете умножение (n * whatever was returned by factorial), и вы заканчиваете путь B этого вызова и возвращаете r .

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

factorial(5)
  factorial(4)
    factorial(3)
      factorial(2)
        factorial(1)
        return 1
      return r
    return r
  return r
return r

Answer 2

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

long factorial (long n, std::string prefix= "") // default parameter
  ...
   cout prefix << "Pass A" << endl;
   cout prefix << "n = " << n << endl;
   cout prefix << "r = " << r << endl;

   r = n * factorial (n-1, prefix+ "  "); // increase indentation
   ...etc...

Мое использование std :: string может быть немного странным, но вы поймете идею. Ваш вывод должен выглядеть следующим образом.

Please type a number: 4

Pass A
n = 4
r = 0
  Pass A
  n = 3
  r = 0
    Pass A
    n = 2
    r = 0
    Pass B
    n = 2
    r = 2
  Pass B
  n = 3
  r = 6
Pass B
n = 4
r = 24

4! = 24

Answer 3

Потому что тогда рекурсия перематывается.

Может быть, было бы проще подумать о случае, когда n равен 2. В этом случае вы вводите условный блок и выполняете повторную процедуру после «Пропуска А». Когда вы набираете n, это 1, и вы возвращаетесь через блок else. Когда вы вернетесь, вы вернетесь к предыдущему кадру рекурсии, где n равно 2. r обновляется в соответствии с результатом рекурсивного вызова, 2*1, но n остается 2, как в предыдущий кадр.

factorial(2)
  factorial(1)
factorial(2)

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

factorial(3)
  factorial(2)
    factorial(1)  // returns 1
  factorial(2)    // r=2*1
factorial(3)      // r=3*2

Answer 4

Значение n в проходе A и проходе B всегда будет таким же, как вы не меняете его где-либо между ними. Вы передаете n-1 рекурсивному вызову, но это не меняет значение n.

Причина, по которой вы можете запутаться, заключается в том, что вы не видите проход A и пропуск B для данного n (n>2) рядом друг с другом.

When n=2, you'll see:
pass A for n=2
pass B for n=2

When n=3, you'll see:
pass A for n=3
pass A for n=2 // cuz of recursive call.
pass B for n=2
pass B for n=3 // looks like n has increment here..but this 'pass B' pairs with first pass A

Answer 5

Пропуск B печатается, когда он «раскручивает» рекурсию. Это повторялось до тех пор, пока не достигло «else return (1);» часть, а затем начал отступать. Поскольку при каждом входе он вызывал себя на единицу меньше для n, он, по-видимому, увеличивается при отступлении.

Answer 6

Если вы заметили, Pass B на самом деле не проходит через функцию во второй раз, он только печатает результаты рекурсии.

So A печатает 4, 3, 2 и т. Д., В то время как backwords B печатает4 3 2 1 (т.е. 2 3 4)

Please type a number: 4
Pass A
n = 4
r = 0
Pass A
n = 3
r = 0
Pass A
n = 2
r = 0
Pass B
n = 2
r = 2
Pass B
n = 3
r = 6
Pass B
n = 4
r = 24
4! = 24
Press any key to continue . . .

Попробуйте заменить второй отпечаток r на

   cout << "Pass B" << endl;  
   cout << "n = " << n << endl;
   cout << "r = " << r << " --- NOTICE RESULT ACCUMULATING AS WE UNNEST THE RECURSION" <<endl;

PS C:\temp> .\r.exe 4
Please type a number: 4
Pass A
n = 4
r = 0
Pass A
n = 3
r = 0
Pass A
n = 2
r = 0
Pass B
n = 2
r = 2 --- NOTICE RESULT ACCUMULATING
Pass B
n = 3
r = 6 --- NOTICE RESULT ACCUMULATING
Pass B
n = 4
r = 24 --- NOTICE RESULT ACCUMULATING
4! = 24
Press any key to continue . . .

Answer 7

Мне кажется, что ваша программа работает правильно и должна вывести что-то вроде этого для числа = 3 (разрывы строк удалены для удобства чтения):

Pass A n = 3 r = 0 [1]

Pass A n = 2 r = 0 [2]

Пропуск B n = 2 r = 2 [3]

Pass B n = 3 r = 6 [4]

Так что я думаю, что вижу, как вы могли бы сделать вывод, что n увеличивается на проходе B, но на самом деле это не так. Необходимо помнить, что n - это локальная переменная функции, поэтому в этом случае n, напечатанное в [3], является РАЗЛИЧНЫМ экземпляром локальной переменной для n в [4].

Значения n, напечатанные в [1] и [4], взяты из верхнего вызова функции (где n = 3), значения, напечатанные в [2] и [3], являются вызовом в верхней версии фактор (то есть n-1).

Answer 8

Вы видите все «Pass A» по порядку, а затем все «Pass B» в обратном порядке, что создает впечатление, что n увеличивается, даже если вы видите только первоначально переданные n.