Укороченные операторы и хвостовая рекурсия

Скажем, у меня есть простая функция:

int all_true(int* bools, int len) {
    if (len < 1) return TRUE;
    return *bools && all_true(bools+1, len-1);
}

Эту функцию можно переписать в более очевидном стиле хвостовой рекурсии следующим образом:

int all_true(int* bools, int len) {
    if (len < 1) return TRUE;
    if (!*bools) return FALSE;
    return all_true(bools+1, len-1);
}

Логически между ними нет никакой разницы; предполагая, что bools содержит только TRUE или FALSE (разумно определенные), они делают то же самое.

Мой вопрос: если компилятор достаточно умен, чтобы оптимизировать второй как хвостовой рекурсивный вызов, разумно ли ожидать, что он оптимизирует первый таким же образом, учитывая, что "&&" короткие замыкания? Очевидно, что если бы использовался оператор без короткого замыкания, это не было бы хвостовой рекурсией, потому что оба выражения будут оцениваться еще до того, как оператор будет применен, но мне любопытно, что такое короткое замыкание. кейс.

(Прежде чем я получу поток комментариев, говорящих мне, что компиляторы C обычно не оптимизируют хвостовые рекурсивные вызовы: считайте, что это общий вопрос об оптимизации хвостовых рекурсивных вызовов с помощью операторов короткого замыкания, независимо от языка. Я буду буду рад переписать это на Scheme, Haskell, OCaml, F#, Python или на чем еще, если вы не понимаете C.)


recursion compiler-optimization short-circuiting tail-recursion
person koschei    schedule 15.12.2011    source источник
comment
gcc оптимизирует рекурсивные вызовы.   -  person Arafangion    schedule 15.12.2011

Ответы (1)


arrow_upward
2
arrow_downward

Ваш вопрос действительно "насколько умен компилятор?" но вы не указываете, какой компилятор вы используете.

При наличии гипотетического разумного компилятора, который преобразует исходный код в промежуточный потоковый граф перед оптимизацией, оба написанных вами фрагмента кода могут быть представлены одинаково (оператор &&, хотя и удобен для ввода, не так тривиально компилируется, как оператор & оператор; поэтому я не удивлюсь, если он будет расширен за одну фазу на гипотетическом компиляторе). Исходя из этого предположения, разумно утверждать, что ответ на ваш вопрос «да».

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

person Conrad Irwin    schedule 15.12.2011