Загадочный переполнение стека

Question

Итак, я написал программу, которая использует алгоритм евклида, чтобы найти GCD's 2 ints.

Пользователь вводит один int (n), тогда программа принимает все возможные комбинации целых чисел между 8 и n, находит их соответствующие GCD (рекурсивно) и печатает, какие вычисления GCD требовали большинства операций модуля.

Я получил программу, работающую, но я получаю переполнение стека около п = 50, и он должен работать, по крайней мере, 3000.

Я рассмотрел мой код на некоторое время и не могу найти проблему ,

#include<iostream> 
#include <math.h> 
using namespace std; 

int cost, gcd, greatestCost, n, beginningA, beginningB, finalA, finalB, finalGCD, iteration; 

void findGCD(int num1, int num2, int startingCost) { 
    //findGCD 
    //finds GCD of every combination (a,b) from i to n 
    //prints those with the greatest number of modulus operations 
    int a = num1; 
    int b = num2; 
    cost = startingCost; 

    cost++; 
    if (b%a > 0) { 
     //cout << "gcd(" << b << "," << a << ") = "; 
     findGCD(b%a, a, cost); 
    }  
    else { 
      gcd = a; 

      if (cost > greatestCost) { 
       greatestCost = cost; 
       finalA = beginningA; 
       finalB = beginningB; 
       finalGCD = gcd; 
      } 
      //cout << "gcd(" << b << "," << a << ") = " << gcd << " With a cost of: " << cost << endl; 

      //do next iteration (2,8), (3,8) etc... 
      if (++beginningA <= beginningB) {   //beginning A goes from 1-i first 
       findGCD(beginningA, beginningB, 0); 

      } 
      else { 
        if (beginningA <= n) {  //begin next cycle with new b value (1,9), (2,9) while b <= n 
         beginningA = 1;      //reset to 1 so it will increment from 1-i again 
         cout << "At i=" << iteration++ << "; gcd(" << finalA << "," << finalB << ") = " << finalGCD << 
           " took " << greatestCost << " modulus operations" << endl; 
         findGCD(beginningA, ++beginningB, 0);   
        } 
        else //When it tries to continue iterating with a number > n 
          //print the last, most intensive, iteration and stop 
         cout << "At i=" << iteration++ << "; gcd(" << finalA << "," << finalB << ") = " << finalGCD << 
         " took " << greatestCost << " modulus operations" << endl; 
        } 
     } 
} 

int main() { 

    greatestCost = 0;  //cost of the iteration with the most modulus operations 
    beginningA = 1;   
    beginningB = 8; 
    iteration = 8; 

    cout << "Enter an integer greater than 8 " << endl; //receive n from user 
    cin >> n; 

    if (n <= beginningB)        //begin GCD search, granted user input > 8 
     cout << "Error!!! integer must be greater than 8"; 
    else 
     findGCD(beginningA, beginningB, 0);  //algorithm begins at (1,8) 

    return 0; 
} 

На данный момент единственное, что я могу думать, как проблема является то, что я сделал в C++, что я не должен (я новичок в C++ и передается по от Явы)

Sample Output

Что я пробовал:

• расщепление функции НОД в 2
• передавая только ссылки с помощью Функции

Answer 1

Прежде всего, ваше объяснение остается неясным, от вас коды, я понял, что для каждого 8<=i<=n вы принять все возможные x, y где y<=i и x<=y и расчет, которые требуют НОД большинство шагов.

Я переписал ваш код, чтобы findGCD обнаружил только gcd из 2-го числа, увеличив при этом некоторую глобальную переменную стоимости.

#include<iostream> 
#include <math.h> 
using namespace std; 

int cost, gcd, greatestCost, n, beginningA, beginningB, finalA, finalB, finalGCD, iteration; 

int findGCD(int a, int b) { 
    cost++; 
    if (b%a > 0) 
     return findGCD(b%a, a); 
    else 
     return a; 
} 

int main() { 

    greatestCost = 0;  //cost of the iteration with the most modulus operations 
    beginningA = 1;   
    beginningB = 8; 
    iteration = 8; 

    cout << "Enter an integer greater than 8 " << endl; //receive n from user 
    cin >> n; 

    if (n <= beginningB)        //begin GCD search, granted user input > 8 
     cout << "Error!!! integer must be greater than 8"; 
    else { 
     for (int i = beginningB; i <= n; i++) { 
      int greatestCost = 0, gcd0 = 1, i0 = 0, j0 = 0; 
      for (int t = beginningB; t <= i; t++) 
       for (int j = 1; j <= t; j++) { 
        cost = 0; 
        int gcd = findGCD(j, t); 
        if (cost > greatestCost) { 
         greatestCost = cost; 
         gcd0 = gcd; 
         i0 = t; 
         j0 = j; 
        } 
       } 

      cout << "At i=" << i << "; gcd(" << j0 << "," << i0 << ") = " << gcd0 << 
            " took " << greatestCost << " modulus operations" << endl; 

     } 
    } 
    return 0; 
} 

Answer 2

Переполнение стека вы получаете вызвано использованием слишком рекурсивных вызовов: Каждый раз, когда вы вызываете функцию новый фрейм стека (проведение локальных переменных, параметров и, возможно, другие вещи) создается в (вызов). Этот кадр освобождается только при возврате (обычно или через исключение) из функции. Но с рекурсивными вызовами вы не возвращаетесь с первого вызова функции перед возвратом из второго, который, в свою очередь, возвращается только после третьего и так далее. Таким образом, стек стека накапливается в стеке, который обычно имеет размер около 8 кБ, пока не будет использована вся доступная память для стека: это переполнение стека (вы слишком много накладываете на него, тем самым переполняя его).

Это может быть решен с помощью итерации (с помощью петли) вместо того, чтобы:

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

Вычисление наибольшего общего делителя и его стоимость должны быть учтены в функции.

Осталось только вызывать эту функцию из петель, а некоторые - отслеживать максимум.

#include <iostream> 
#include <vector> 
#include <utility> 
using namespace std; 

unsigned gcd(unsigned a, unsigned b, unsigned * const cost) { 
    if (cost) { 
    *cost = 0; 
    } 
    while (b != 0) { 
    auto const rest = a % b; 
    if (cost) { 
     ++(*cost); 
    } 
    a = b; 
    b = rest; 
    } 
    return a; 
} 

int main() { 
    unsigned const n = 3500; 
    unsigned greatestCost = 0; 
    vector<pair<unsigned, unsigned>> pairs; 
    for (unsigned b = 8; b <= n; ++b) { 
    for (unsigned a = 0; a <= b; ++a) { 
     unsigned cost; 
     gcd(a, b, &cost); 
     if (cost == greatestCost) { 
     pairs.emplace_back(a, b); 
     } else if (cost > greatestCost) { 
     pairs.clear(); 
     pairs.emplace_back(a, b); 
     greatestCost = cost; 
     } 
    } 
    } 
    cout << "Greatest cost is " << greatestCost << " when calculating the GCD of " << endl; 
    for (auto const & p : pairs) { 
    cout << "(" << p.first << ", " << p.second << ")" << endl; 
    } 
    return 0; 
} 

(Live)

Примечание, в частности, что я не использую любой глобальной переменной.

---

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

К сожалению, эта оптимизация довольно сложна для реализации на языке C++ по различным причинам.

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

---

Как заключительное примечание: Вы могли бы реализовать вычисление НОД с помощью рекурсивных вызовов здесь, так как вы видите, максимальная глубина будет 17 + 1, который должен быть достаточно мал, чтобы поместиться на любой (за пределами встроенных систем) стек вызовов , Тем не менее, я по-прежнему придерживаюсь итеративной версии: она имеет лучшую производительность, лучше подходит для идиомы языка и является «более безопасным» способом.