Функциональность рекурсивной функции в C ++ - PullRequest
Новая
       7

Функциональность рекурсивной функции в C ++

0 голосов
/ 17 ноября 2018

Я нашел функцию рекурсии на сайте GeeksforGeeks.Может кто-нибудь объяснить, как работает эта функция? 

int fun1(int x, int y)
{ 
   if(x == 0) 
       return y; 
   else
      return fun1(x - 1, x + y); 
}

Он говорит, что вернет y + (x + x-1 + x-2 + x-3 + ... 2 + 1).Я ценю, если кто-то может объяснить, почему.Я думал, что он должен вернуть y + 1, так как когда x становится 1 в памяти стека, он возвращает y + 1 (поскольку x-1 становится 0), и в конце концов он будет возвращать другие функции в стеке как y + 1 до начала первогофункция.

1 Ответ

0 голосов
/ 17 ноября 2018

Вы правы, что когда x == 1, это возвращает y+1.Но для других случаев помните, что y также отличается между вызовами.Например, когда x==2, он вызывает fun1(2 - 1, 2 + y), поэтому для следующего вызова y на два больше, чем было раньше.Этот следующий вызов имеет x == 1, поэтому он возвращает на единицу больше, чем y, что само по себе на 2 больше исходного значения, поэтому вызов fun1(2, y) возвращает y + 2 + 1.

Иллюстрация стека вызовов может быть более полезной.Допустим, мы вызываем fun1(5, 7).

  • fun1(5, 7), возвращает значение fun1(5 - 1, 5 + 7)
  • fun1(4, 12), возвращает значение fun1(4 - 1, 4 + 12)
  • fun1(3, 16) возвращает значение fun1(3 - 1, 3 + 16)
  • fun1(2, 19) возвращает значение fun1(2 - 1, 2 + 19)
  • fun1(1, 21) возвращает значение fun1(1 - 1, 1 + 21)
  • fun1(0, 22)возвращает 22.

Таким образом, все вместе (и немного переставляя) вызов fun1(5, 7) возвратил 7 + (5 + 4 + 3 + 2 + 1), как сказано в документации.

...