Реализация функции Tak с использованием хвостовой рекурсии

Оптимизация хвостовой рекурсии в C++ требует, чтобы был только 1 рекурсивный вызов (что в основном позволяет преобразовать его в цикл), и этот рекурсивный вызов был последней операцией в функции:

Пример:

unsigned int f( unsigned int a ) 
{
   if ( a == 0 ) 
   {
      return a;
   }
   return f( a - 1 );   // tail recursion
}

Поскольку функция Tak требует 4 рекурсивных вызова на «итерацию»:

int tak(int x, int y, int z)
{
    if (x >= y)
    {
        return z;
    }
    else
    {
        return tak(tak(x-1, y, z), tak(y-1, z, x), tak(z-1, x, y)); // this is why it cannot happen
    }
}

Как видите, последний вызов рекурсивный, но внутри него 3 рекурсивных вызова. Это предотвращает оптимизацию хвостовой рекурсии (и нет логического метода для преобразования этого в нерекурсивный цикл, который требуется для оптимизации хвостовой рекурсии).

Другой способ его реализации:

int tak(int x, int y, int z)
{
    while (x > y) 
    {
        int oldx = x, oldy = y;
        x = tak(x - 1, y, z);
        y = tak(y - 1, z, oldx);
        if (x <= y) 
            break;
        z = tak(z - 1, oldx, oldy);
    }
    return z;
}

Что еще раз показывает, что даже в форме цикла он по-прежнему рекурсивен, что предотвращает оптимизацию хвостовой рекурсии.

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

int tak(int x, int y, int z){
    if(x>y)
        return tak(tak(1-x,y,z), tak(y-1,z,x), tak(z-1,x,y));
    else
        return z;
} 

Однако вы не можете сделать это с хвостовой рекрузией, поскольку ее нельзя преобразовать в петлю. Так как существует более одного вызова рекрузии.