Опитах се да търся, но не можах да намеря: какви са реквизитите за функции, така че gcc да оптимизира рекурсията на опашката? Има ли препратка или списък, който да съдържа най-важните случаи? Тъй като това е специфично за версията, моите интереси са 4.6.3 или по-нови версии (по-новите, толкова по-добре). Всъщност, всяко конкретно позоваване би било много ценено.
Благодаря предварително!
Отговори:
13 за отговор № 1с -O2 gcc ще извърши оптимизация на опашката, ако е възможно. Сега въпросът е: Кога е възможно?
Възможно е да се елиминира сингъл рекурсивно повикване, когато рекурсивното повикване се случи или непосредствено преди, или вътре в (единичната) return изявление, така че след това няма видими странични ефекти, различни от евентуално връщане на различна стойност. Това включва връщане на изрази, включващи тройния оператор.
Имайте предвид, че дори и да има такива няколко рекурсивни обаждания в израза за връщане (като например в добре познатия пример на Fibonacci: return (n==1) ? 1 : fib(n-1)+fib(n-2);), рекурсията на опашката се използва все още, но само до последното рекурсивно повикване.
Като очевиден специален случай, ако компилаторът можедоказва, че рекурсивната функция (и нейните аргументи) се квалифицират като постоянно изразяване, тя може (до конфигурируема максимална дълбочина на рекурсията по подразбиране 500) да елиминира не само опашката, но и цялото изпълнение на функцията. Това е нещо, което ССЗ прави рутинно и съвсем надеждно -O2, който дори включва повиквания към определени библиотечни функции, като например strlen върху литералите.