Как подсчитать вызовы рекурсивной функции (Increment by 1) | C++

Question

У меня есть следующий код, как показано ниже. Он принимает ввод и печатает строки за строкой, чтобы решить проблему Ханоя. Все, что я хочу сделать, это напечатать в каждой строке step1, step2 и так далее, от 1 до конца шагов, как на примере ниже:

Введите число дисков: 3
Шаг 1: 1 -> 2 Переместите один диск с оригинальной привязки на дополнительный привязку
Шаг 2: 1 -> 3 Переместите один диск с исходного колышка на пункт назначения
Шаг 3: 2 -> 3 Переместите один диск из дополнительная привязка к месту назначения привязывают

#include <iostream> 
int count=1; 
    void ToH(int dskToMv, int cLocation, string orpeg, int tmpLocation, string expeg, int fLocation, string depeg) 
    { 
     if(dskToMv != 0) 
     { 
count++; 
      ToH(dskToMv-1, cLocation, orpeg, fLocation, depeg, tmpLocation, expeg); 
      cout<<"Step "<<count<<": Move one disk from the "<< orpeg << " to the " << depeg 
       << " " << cLocation << " -> " << fLocation << endl; 
      ToH(dskToMv-1, tmpLocation, expeg, cLocation, orpeg, fLocation, depeg); 
     } 
    } 

    int main() 
    { 
     int c; 
     cout << "Enter the number of disks: "; 
     cin >> c; 
     ToH(c, 1, "original peg ", 2, "extra peg", 3, "destination peg"); 
    } 

Answer 1

в рекурсии, когда вам нужно «держать» след что-то на одну итерацию, есть несколько способов:

1. Примитивные глобальные переменные - Они позволяют только единичные состояния будут сохранены. Если ветви рекурсии и т. Д., Она может не работать, потому что одна ветвь перезапишет значение, используемое другой ветвью. Для простого хранения таких вещей, как counts, и такие, как правило, работают хорошо.

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

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

Все, что вам нужно сделать, это объявить глобальный int и затем увеличить его в вызове функции. Каждый раз, когда функция вызывается, значение увеличивается и, следовательно, подсчитывает количество вызовов функций. Поскольку он только увеличивается, у нас нет проблем с ветвлением (так как каждая ветка будет делать то же самое и, следовательно, быть неразличимой).

int count = 0; 
void ToH(int dskToMv, int cLocation, string orpeg, int tmpLocation, string expeg, int fLocation, string depeg) 
{ 
    count++; 
    if(dskToMv != 0) 
    { 
     ToH(dskToMv-1, cLocation, orpeg, fLocation, depeg, tmpLocation, expeg); 
     cout<<" Move one disk from the "<< orpeg << " to the " << depeg 
      << " " << cLocation << " -> " << fLocation << " - " << count << endl; 
     ToH(dskToMv-1, tmpLocation, expeg, cLocation, orpeg, fLocation, depeg); 
    } 
} 

В качестве альтернативы, если вы хотите, чтобы для возвратов и, следовательно, на самом деле считать «уровни», вы можете просто использовать параметр:

void ToH(int dskToMv, int cLocation, string orpeg, int tmpLocation, string expeg, int fLocation, string depeg, int count = 0) 
{ 
    if(dskToMv != 0) 
    { 
     ToH(dskToMv-1, cLocation, orpeg, fLocation, depeg, tmpLocation, expeg, count + 1); 
     cout<<" Move one disk from the "<< orpeg << " to the " << depeg 
      << " " << cLocation << " -> " << fLocation << " - " << count << endl; 
     ToH(dskToMv-1, tmpLocation, expeg, cLocation, orpeg, fLocation, depeg, count + 1); 
    } 
} 

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

Answer 2

Вы можете попробовать использовать статическую переменную. Увеличение этой переменной при каждом вызове функции (рекурсивно).

#include <iostream> 

void ToH(int dskToMv, int cLocation, string orpeg, int tmpLocation, string expeg, int fLocation, string depeg) 
{ 
    static int count=0 
    if(dskToMv != 0) 
    { 
     count++; 
     ToH(dskToMv-1, cLocation, orpeg, fLocation, depeg, tmpLocation, expeg); 
     cout<<"Step "<<count<<": Move one disk from the "<< orpeg << " to the " << depeg 
      << " " << cLocation << " -> " << fLocation << endl; 
     ToH(dskToMv-1, tmpLocation, expeg, cLocation, orpeg, fLocation, depeg); 
    } 
} 

int main() 
{ 
    int c; 
    cout << "Enter the number of disks: "; 
    cin >> c; 
    ToH(c, 1, "original peg ", 2, "extra peg", 3, "destination peg"); 
} 

Надеется, что это помогает