Бьерн Страуструп "Язык программирования С++" 3-е издание, стр. 186, п. 7.1.1 "Определения функций".
Сначала приводится пример:
inline int fac(int n) {return (n < 2) ? 1 : n * fac(n-1); }
а потом написано следующее:
В виду допустимости рекурсивных и взаимно рекурсивных встроенных функций, невозможно гарантировать, что в месте каждого вызова такой функции будет действительно осуществлено встраивание кода функции.
Поясните, пожалуйста, КАК рекурсивная функция вообще может быть встраиваемой ?
Каким же будет тогда механизм её вызова ?
Кстати, в Visual C++ 6 SP5 я создал такой файл:
inline int fac(int n) {return (n < 2) ? 1 : n * fac(n-1); }
int main(){
fac(6);
return 0;
}
P.S. Быть может, это не такая уж и серьёзная и часто возникающая проблема, но я задался целью прочесть всего Страуструпа, поэтому не хотелось бы, чтобы у меня оставались "белые пятна".
F_G>inline int fac(int n) {return (n < 2) ? 1 : n * fac(n-1); }
F_G>
F_G>а потом написано следующее: F_G>
F_G>В виду допустимости рекурсивных и взаимно рекурсивных встроенных функций, невозможно гарантировать, что в месте каждого вызова такой функции будет действительно осуществлено встраивание кода функции.
F_G>Поясните, пожалуйста, КАК рекурсивная функция вообще может быть встраиваемой ? F_G>Каким же будет тогда механизм её вызова ?
F_G>Кстати, в Visual C++ 6 SP5 я создал такой файл:
[]
F_G>[/asm] F_G>То есть встраивания не произошло, как я и ожидал
F_G>P.S. Быть может, это не такая уж и серьёзная и часто возникающая проблема, но я задался целью прочесть всего Страуструпа, поэтому не хотелось бы, чтобы у меня оставались "белые пятна".
F_G>inline int fac(int n) {return (n < 2) ? 1 : n * fac(n-1); }
F_G>
F_G>а потом написано следующее: F_G>
F_G>В виду допустимости рекурсивных и взаимно рекурсивных встроенных функций, невозможно гарантировать, что в месте каждого вызова такой функции будет действительно осуществлено встраивание кода функции.
F_G>Поясните, пожалуйста, КАК рекурсивная функция вообще может быть встраиваемой ? F_G>Каким же будет тогда механизм её вызова ?
Ничто не мешает достаточно умному компилятору "раскрутить" рекурсию в цикл.
Любой рекурсивный вызов можно преобразовать в цикл. Другое дело, что такого рода цикл не будет, вероятно, быстрее рекурсии — все равно придется каким-то образом организовывать стек и взаимодействовать с ним на каждой итерации.
Да здравствует мыло душистое и веревка пушистая.
Re: Как рекурсивная функция может быть inline ?
От:
Аноним
Дата:
16.02.04 10:25
Оценка:
Здравствуйте, Forrest_Gump, Вы писали:
F_G>
F_G>В виду допустимости рекурсивных и взаимно рекурсивных встроенных функций, невозможно гарантировать, что в месте каждого вызова такой функции будет действительно осуществлено встраивание кода функции.
F_G>Поясните, пожалуйста, КАК рекурсивная функция вообще может быть встраиваемой ? F_G>Каким же будет тогда механизм её вызова ?
Так о том и говорится, что не может. Имеется в виду, что директива inline носит не обязательный характер, а только как рекомендация компилятору.
Re[2]: Как рекурсивная функция может быть inline ?
Здравствуйте, Аноним, Вы писали:
А>Здравствуйте, Forrest_Gump, Вы писали:
F_G>>
F_G>>В виду допустимости рекурсивных и взаимно рекурсивных встроенных функций, невозможно гарантировать, что в месте каждого вызова такой функции будет действительно осуществлено встраивание кода функции.
F_G>>Поясните, пожалуйста, КАК рекурсивная функция вообще может быть встраиваемой ? F_G>>Каким же будет тогда механизм её вызова ?
А>Так о том и говорится, что не может. Имеется в виду, что директива inline носит не обязательный характер, а только как рекомендация компилятору.
Очень даже может.
тоже же хрестоматийный вызов fac(5) может быть преобразован путем встраивания в 5*fac(4), а может и в 5*4*fac(3), а может и до конца вычислить и записать сразу константу куда запрошено.
Все зависит от качества компилятора.
Здравствуйте, jazzer, Вы писали: J>Очень даже может. J>тоже же хрестоматийный вызов fac(5) может быть преобразован путем встраивания в 5*fac(4), а может и в 5*4*fac(3), а может и до конца вычислить и записать сразу константу куда запрошено. J>Все зависит от качества компилятора
А если в коде встречается вызов не fac(5), а fac(x), где х — целая переменная, а не константа ?
Re[4]: Как рекурсивная функция может быть inline ?
Здравствуйте, Forrest_Gump, Вы писали:
F_G>Здравствуйте, jazzer, Вы писали: J>>Очень даже может. J>>тоже же хрестоматийный вызов fac(5) может быть преобразован путем встраивания в 5*fac(4), а может и в 5*4*fac(3), а может и до конца вычислить и записать сразу константу куда запрошено. J>>Все зависит от качества компилятора
F_G>А если в коде встречается вызов не fac(5), а fac(x), где х — целая переменная, а не константа ?
По-любому, правая рекурсия без труда превращается в итерацию.
Но как только у нас будут неассоциативные операции (даже вычитание) — обломс.
Конечно, можно развернуть F(x) = p(x) ? g(x) : h(x) + k(x)*F(s(x))
в такую систему
if(p(x)) return g(x);
result_t v; scale_t z;
v = h(x); z = k(x); x = s(x);
while(true)
{
if(p(x)) return v + z*g(x);
v += h(x); z *= k(x); x = s(x);
}
но для этого нужна ассоциативность k1*(k2*k3)=(k1*k2)*k3 и дистрибутивность k*(h+f) = k*h + k*f.
Так что если рекурсию F(x) = p(x) ? g(x) : R(x,F(s(x)))
R(x,F(s(x))) удастся представить в виде бинома (найдя не только коэффициенты, но, возможно, и подходящие операции) — тогда велкам!
А если нет — плачь.
Перекуём баги на фичи!
Re[3]: Как рекурсивная функция может быть inline ?
Здравствуйте, jazzer, Вы писали:
F_G>>>Поясните, пожалуйста, КАК рекурсивная функция вообще может быть встраиваемой ? F_G>>>Каким же будет тогда механизм её вызова ?
А>>Так о том и говорится, что не может. Имеется в виду, что директива inline носит не обязательный характер, а только как рекомендация компилятору.
J>Очень даже может. J>тоже же хрестоматийный вызов fac(5) может быть преобразован путем встраивания в 5*fac(4), а может и в 5*4*fac(3), а может и до конца вычислить и записать сразу константу куда запрошено. J>Все зависит от качества компилятора.
Да, есть даже уже классический алгоритм преобразования так называемой хвостовой рекурсии в цикл. Это как раз типичный пример с факториалом сюда подходит. Так что компилятор запросто может для рекурсивной функции генерить цикл, который может развернуть в inline-код.
Хочешь быть счастливым — будь им!
Без булдырабыз!!!
Re[5]: Как рекурсивная функция может быть inline ?
Здравствуйте, LaptevVV, Вы писали:
L> Да, есть даже уже классический алгоритм преобразования так называемой L> хвостовой рекурсии в цикл. <...>
Еще проще: часто компиляторы подставляют рекурсивные вызовы на некоторую
глубину (3-4). В результате, скажем рекурсия вложенности 3, требовавшая 3
вызова, будет осуществлена за 1 вызов. Т.е. если функция определена так:
Здравствуйте, Павел Кузнецов, Вы писали:
L>> Да, есть даже уже классический алгоритм преобразования так называемой L>> хвостовой рекурсии в цикл. <...>
ПК>Еще проще: часто компиляторы подставляют рекурсивные вызовы на некоторую ПК>глубину (3-4). В результате, скажем рекурсия вложенности 3, требовавшая 3 ПК>вызова, будет осуществлена за 1 вызов. Т.е. если функция определена так: ПК>
всюду в предыдущем сообщении я подразумевал, что + и * это произвольные операции, на которые наложено единственное ограничение:
ассоциативность +
ассоциативность *
дистрибутивность слева *(+)
(не помню — нужна в кольце коммутативность или нет; здесь — не нужна).
Известно, что таковы:
арифметические +,* -- кольцо над целыми/вещественными/комплексными числами (а также кольца вычетов по модулю над целыми)
булевы ||,&& -- булева алгебра является субклассом кольца
битовые |,& и ^,& -- соответственно, булева алгебра и кольцо вычетов по модулю 2 в векторном пространстве (целое число как вектор двоичных чисел — разрядов).
Но никто не мешает написать свои функции tipa_plus(lhs,rhs) и tipa_zvezda(lhs,rhs)
(И после этого — кто-то ещё спрашивал, нафига спецразделы высшей математики программисту).
Перекуём баги на фичи!
Re[5]: Как рекурсивная функция может быть inline ?
Здравствуйте, Павел Кузнецов, Вы писали:
ПК>Еще проще: часто компиляторы подставляют рекурсивные вызовы на некоторую ПК>глубину (3-4). В результате, скажем рекурсия вложенности 3, требовавшая 3 ПК>вызова, будет осуществлена за 1 вызов. Т.е. если функция определена так:
В студии это даже можно регулировать
Врубаем встраивание рекурсивных функций
#pragma inline_recursion(on)
Указываем глубину встраивания
#pragma inline_depth(8)
... << RSDN@Home 1.1.3 beta 1 >>
Пусть это будет просто:
просто, как только можно,
но не проще.
(C) А. Эйнштейн
Re[6]: Как рекурсивная функция может быть inline ?
Здравствуйте, Кодт, Вы писали:
К>Здравствуйте, Forrest_Gump, Вы писали:
F_G>>Скажи мне, ГДЕ ты всё это прочёл ?
К>Маломало три курса высшей математики, знание корней° и немного эха в голове.
Что за вуз ? МГУ ? Физтех ?
P.S. Форуму явно нужен тэг [off][/off]
Re[6]: Как рекурсивная функция может быть inline ?
Здравствуйте, Кодт, Вы писали:
К>(не помню — нужна в кольце коммутативность или нет; здесь — не нужна).
Идеалы бывают левыми и правыми: кольцо коммутативно по сложению и не обязательно по умножению.
Re[8]: Как рекурсивная функция может быть inline ?
Здравствуйте, Forrest_Gump, Вы писали:
К>>Маломало три курса высшей математики, знание корней° и немного эха в голове. F_G>Что за вуз ? МГУ ? Физтех ? F_G>P.S. Форуму явно нужен тэг [off][/off]
Здравствуйте, Azir, Вы писали:
A>Здравствуйте, Кодт, Вы писали:
К>>(не помню — нужна в кольце коммутативность или нет; здесь — не нужна). A>Идеалы бывают левыми и правыми: кольцо коммутативно по сложению и не обязательно по умножению.
Да, спасибо. Я уже в справочник слазил.
В общем, здесь ещё недокольцо: уже две операции, ассоциативность, односторонняя дистрибутивность. Обратимость, кстати, тоже не нужна.
Интересно, для булевых функций какие ещё варианты бывают?
Перекуём баги на фичи!
Re[6]: Как рекурсивная функция может быть inline ?
Здравствуйте, WolfHound, Вы писали:
WH>В студии это даже можно регулировать WH>Врубаем встраивание рекурсивных функций WH>#pragma inline_recursion(on) WH>Указываем глубину встраивания WH>#pragma inline_depth(8)
Ага, и вот что получается. На фиг, на фиг такое чудо.
_TEXT SEGMENT
$T13978 = -8 ; size = 4
$T13924 = -4 ; size = 4
_n$ = 8 ; size = 4
?fac@@YAHH@Z PROC NEAR ; fac, COMDAT
; 12 : int fac(int n) { return (n>1)?fac(n-1)*n:1; }
sub esp, 8
push esi
mov esi, DWORD PTR _n$[esp+8]
cmp esi, 1
jle $L13834
lea eax, DWORD PTR [esi-1]
cmp eax, 1
jle $L13980
lea edx, DWORD PTR [eax-1]
cmp edx, 1
mov DWORD PTR $T13978[esp+12], edx
jle $L13983
lea eax, DWORD PTR [edx-1]
cmp eax, 1
jle $L13986
lea ecx, DWORD PTR [eax-1]
cmp ecx, 1
mov DWORD PTR $T13924[esp+12], ecx
jle $L13989
push ebp
lea ebp, DWORD PTR [ecx-1]
cmp ebp, 1
jle $L13992
push ebx
lea ebx, DWORD PTR [ebp-1]
cmp ebx, 1
jle $L13995
push edi
lea edi, DWORD PTR [ebx-1]
cmp edi, 1
jle SHORT $L13998
lea esi, DWORD PTR [edi-1]
cmp esi, 1
jle SHORT $L14001
lea eax, DWORD PTR [esi-1]
push eax
call ?fac@@YAHH@Z ; fac
imul eax, esi
imul eax, edi
mov ecx, DWORD PTR $T13924[esp+28]
imul eax, ebx
mov edx, DWORD PTR $T13978[esp+28]
imul eax, ebp
mov esi, DWORD PTR _n$[esp+24]
imul eax, ecx
lea ecx, DWORD PTR [edx-1]
imul eax, ecx
imul eax, edx
lea ecx, DWORD PTR [esi-1]
add esp, 4
imul eax, ecx
pop edi
imul eax, esi
pop ebx
pop ebp
pop esi
add esp, 8
ret 0
$L14001:
mov eax, 1
imul eax, edi
imul eax, ebx
imul eax, ebp
mov esi, DWORD PTR _n$[esp+20]
imul eax, ecx
lea ecx, DWORD PTR [edx-1]
imul eax, ecx
imul eax, edx
lea ecx, DWORD PTR [esi-1]
imul eax, ecx
pop edi
imul eax, esi
pop ebx
pop ebp
pop esi
add esp, 8
ret 0
$L13998:
mov eax, 1
imul eax, ebx
imul eax, ebp
imul eax, ecx
lea ecx, DWORD PTR [edx-1]
imul eax, ecx
imul eax, edx
lea ecx, DWORD PTR [esi-1]
imul eax, ecx
pop edi
imul eax, esi
pop ebx
pop ebp
pop esi
add esp, 8
ret 0
$L13995:
mov eax, 1
imul eax, ebp
imul eax, ecx
lea ecx, DWORD PTR [edx-1]
imul eax, ecx
imul eax, edx
lea ecx, DWORD PTR [esi-1]
imul eax, ecx
pop ebx
imul eax, esi
pop ebp
pop esi
add esp, 8
ret 0
$L13992:
mov eax, 1
imul eax, ecx
lea ecx, DWORD PTR [edx-1]
imul eax, ecx
imul eax, edx
lea ecx, DWORD PTR [esi-1]
imul eax, ecx
pop ebp
imul eax, esi
pop esi
add esp, 8
ret 0
$L13989:
lea ecx, DWORD PTR [edx-1]
mov eax, 1
imul eax, ecx
imul eax, edx
lea ecx, DWORD PTR [esi-1]
imul eax, ecx
imul eax, esi
pop esi
add esp, 8
ret 0
$L13986:
mov eax, 1
imul eax, edx
lea ecx, DWORD PTR [esi-1]
imul eax, ecx
imul eax, esi
pop esi
add esp, 8
ret 0
$L13983:
lea ecx, DWORD PTR [esi-1]
mov eax, 1
imul eax, ecx
imul eax, esi
pop esi
add esp, 8
ret 0
$L13980:
mov eax, 1
imul eax, esi
pop esi
add esp, 8
ret 0
$L13834:
mov eax, 1
pop esi
add esp, 8
ret 0
?fac@@YAHH@Z ENDP ; fac
_TEXT ENDS