Хвостовая рекурсия [C]

Question

Вопрос в моей книге: "Какие из рекурсивных вызовов (не функций!) Являются хвостовыми рекурсивными?"

unsigned f(unsigned x) 
{ 
    if(x==0) return 1; 
    else if(x==1) return f(x-1); 
    else return 3*x + f(x-1); 
}

В этом примере я предполагаю, что первый - хвостовой рекурсивный, а второй - нет. Однако, что происходит в следующем случае, где мы также имеем printf() до и после рекурсивного вызова (ов)?

void f(unsigned x) 
{
    if(x==0) return;
    else if(x==1) { f(x-1); printf("1"); }
    else if(x==2) { printf("2"); f(x-1); }
    else f(x-3);
}

Учитывая то, что я до сих пор знаю о хвостовой рекурсии, я предположил, что первый нет, а второй и третий - нет? Я не прав, и если да, не могли бы вы объяснить, как это работает?

Answer 1

В первом примере вы правы, что только первый вызов потенциально рекурсивен.

Во втором примере первый вызов printf() потенциально является хвостовым вызовом, а второй и третий вызов f() потенциально хвост рекурсивны.

Это зависит от деталей вашей реализации, и хотя используемый ABI может дать подсказку (вот почему вызов f() более вероятно, будет хвост-рекурсивным, чем вызов printf() фальшивый вызов), это доказательство явно слабое.
Стандарт молчит по этим вопросам.