Как отличить хвостовые рекурсивные вызовы/нерегулярные рекурсивные вызовы?

Question

int gcd(int a,int b){ 
    if(a == b) return a; 
    else if (a>b) return gcd(a-b,b); 
    else return gcd(a,b); 
    } 

Например, я думаю, что это хвостовое рекурсивно, потому что вы не вызываете другую функцию.

int gcd(int a,int b){ 
int x; 
    if(a == b) x=a; 
    else if (a>b) x= gcd(a-b,b); 
    else x= gcd(a,b); 
    return x; 
    } 

И это не-хвост, рекурсивный, потому что он вызывает функцию gcd.

Я прав? Или есть ли более простой способ отличить хвостовой/не хвостовой рекурсивный вызов?

Answer 1

Прежде всего, для целей g ++ TCO (оптимизация хвостового вызова) не имеет значения, выполняете ли вы рекурсивный вызов или вызываете другую функцию вообще - вызов функции будет заменен безусловным переходом.

Во-вторых, вызов хвоста происходит, когда между вызовом другой функции и возвратом ничего не происходит. Это может быть последняя строка перед возвратом, а не последняя строка перед возвратом или возвратом.

Например,

} else { 
    x = gcd(a,b); 
    return x; 
} 

является хвост вызова, поскольку значение х возвращается немодифицированного (ничего не происходит).

С другой стороны,

} else { 
    x = gcd(a,b); 
    return x + 1; 
} 

Это не имеет права на совокупную стоимость владения, так как возвращаемое значение изменяется - что-то этого происходит.

Но веселье только начинается! Давайте поговорим о C++ и деструкторах. Рассмотрим следующий код:

int do2(); 

int do() { 
    std::string x; 
    // ... 
    return do2(); 
} 

Это хвост? Первое впечатление - да, это так. Ничего не происходит, не так ли? Второе впечатление - нет, это не так! x Деструктор должен произойти! Третье впечатление - да, это - потому что компилятор, видя как x не используется после вызова, может легко уничтожить x раньше.

Но, посмотрите на это:

int do2(const std::string&); 

int do() { 
    std::string x; 
    // ... 
    return do2(x); 
} 

Вот это не хвост позвони! x должен пережить do2, так что вернуться к моему оригинальному (намеренно расплывчатому) определению, что-то происходит.

Хвост-звонки смешные!