The Euler function. time-limit-exceeded

The program implements the Euler function (https://ru.wikipedia.org/wiki/Функция_Эйлера), everything seems to work, I checked on tests - there were no errors on sufficiently large numbers, including.

The only problem is that I can't pass the program due to time-limit-exceeded (on the first 9 tests, everything works in 2 milliseconds, and on the 10th test-3.076 seconds). The maximum time limit is 3 seconds. Please help, maybe someone will find where I have in the program it can happen?

#include <iostream>
using namespace std;

int binomialCoeff(int k, int n)  
{ 
    if (k == 0 || k == n)  
        return 1;  
  
    return binomialCoeff(k - 1, n - 1) +  
        binomialCoeff(k, n - 1);  
}

int gsd(int a, int b) {
    while(a!=0 && b!=0) {
        if(a>b) a%=b;
        else b%=a;
    }
    return a+b;
}

int Euler(unsigned long k, unsigned long n) {
    unsigned int result=1; 
    int combination = binomialCoeff(k,n);
    for(int i=2; i<=combination; i++) {
        if(gsd(i,combination) == 1) {
            result++;
        }
    }
    return result;
}

int main() {
    int k, n;
    cin >> k >> n;
    if(k<0 || n<0 || n<k) 
        throw invalid_argument("Binom condition failed");
    cout << Euler(k,n);
    return 0;
}