Функция рекурсии в C ++

Question

Если у меня есть эта рекурсивная функция:

int mystery(int n) {

if ( n == 0 || n == 1 ||  n ==  2) return  n ;
 return (mystery(n-1) + mystery(n-2) + mystery(n-3))  ;
}

Я работаю над поиском тайны (20).

Как узнать, сколько операций сложения выполняется при вычислении функции и сколько вызовов mystery () существует для вычисления mystery (20)?

Я попытался добавить несколько операторов cout, таких как:

int mystery(int n) {
    if ( n == 0 || n == 1 ||  n ==  2) {
      cout << n << endl; 
      return  n ;
    }
        cout << n << endl;
    return (mystery(n-1) + mystery(n-2) + mystery(n-3))  ;
}

Но я не мог понять этого, поскольку было выведено более тысячи чисел. И я не верю, что эти операторы cout способствуют тому, чтобы сказать мне, сколько операций сложения выполняется и сколько вызовов mystery () существует для вычисления mystery (20)?

Спасибо за любую помощь!

Answer 1

Самый простой способ сделать это увеличить глобальную (или статическую глобальную) переменную.

Что-то вроде того, чтобы получить номер загадочного звонка:

int nb_of_invok = 0;
int mystery(int n)
{
  nb_of_invok++;
  ...your code here...
}

И это, чтобы получить количество дополнений:

int nb_of_invok = 0;
int nb_of_add = 0;
int mystery(int n)
{
  nb_of_invok++;
  if(...)return n;
  nb_of_add++;
  return(...);
}

Answer 2

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

int mystery(int n) {
    static int invocations = 1;

    cout << "mystery has been invoked " << invocations++ << " times.\n";
    if ( n == 0 || n == 1 ||  n ==  2) {
      return  n ;
    }
    return (mystery(n-1) + mystery(n-2) + mystery(n-3))  ;
}

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

Кстати, не используйте endl, если только это не то, что вы хотите использовать.Это очень медленно, так как вызывает принудительную очистку буфера всякий раз, когда вы его используете.Используйте '\n'.

Answer 3

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

Answer 4

Другой вариант - сделать так, чтобы это был метод класса, который позволял бы использовать переменную-член, а не глобальную, и в то же время поддерживал бы интерфейс int mystery(int) в чистоте.

Answer 5

Использовать (и увеличивать) глобальную переменную. http://www.cplusplus.com/doc/tutorial/variables/

Я бы напечатал пример, но у меня травма руки.

Answer 6

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