/// G. Hagopian working on Euclidean algorithm

//#include "std_lib_facilities.h"
#include <iostream>
using namespace std;
//------------------------------------------------------------------------------
/*
    Brute Force
*/

int gcd(int m, int n, int cntr) {
    if ((m % n) == 0) {  /// base case
        cout << "\nNumber of function calls is " << cntr;
        return n;
    }
    else {
        cout << endl << n;
        ++cntr;
        return gcd(n, m % n, cntr);
    }
}

int dgcd(int m, int n, int cntr)
{
    if(m == n) {  /// base case
        cout << "\nNumber of function calls is " << cntr;
        return m;
    }
    else if(m > n) {
        cout << endl << m-n;
        ++cntr;
        return dgcd(m-n, n, cntr);
    }
    else {
        cout << endl << m;
        ++cntr;
        return dgcd(m, n-m, cntr);
    }
}

int main()
{
    int m {1}, n {1};
    cout << "\nEnter two numbers, m < n, to get the GCD: ";
    while(cin >> m >> n)
    {
        cout << "\nEuclid's algorithm gives gcd(" << n << "," << m
             << ")= " << gcd(n,m,0);
        cout << "\nDykstra's improvement gives gcd(" << n << "," << m
             << ")= " << dgcd(m,n,0);
        cout << "\nEnter two numbers, m < n, to get the GCD: ";
    }
}

//------------------------------------------------------------------------------