Please demonstrate a recursive algorithm for finding the Euler function (preferably in C / C ++, but also in pseudocode)?

Question

Algorithms

Please demonstrate a recursive algorithm for finding the Euler function (preferably in C / C ++, but also in pseudocode)?

Answer 1

GCD function - Euclid's algorithm - write it yourself

typedef long long int enatural;
enatural _euler(enatural n,enatural k)
//шаг рекурсии. n - счетчик по всем числам от 1 до k и условие остановки рекурсии
//k - число, для которого вычисляем функцию Эйлера
{
   //функция Эйлера от 1 равна 1
   if(n==1)
   {
       return(1);
   }
   //функция Эйлера в рекурсивном варианте - если n взаимно просто с k, то она равна 1+(функция Эйлера от n-1)
   if(nod(n,k)==1) //если число взаимно просто, увеличиваем количество
   {
       return(1+_euler(n-1,k));
   }
   //в противном случае она просто равна функции Эйлера от n-1
   return(_euler(n-1,k));
}
enatural euler(enatural n)
{
    return(_euler(n,n));
}