Как рекурсивная функция может быть inline ? - C/C++

Бьерн Страуструп "Язык программирования С++" 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;
}

И, дизассемблер показывает вот что:

2:
3:    int main(){
00401020   push        ebp
00401021   mov         ebp,esp
00401023   sub         esp,40h
00401026   push        ebx
00401027   push        esi
00401028   push        edi
00401029   lea         edi,[ebp-40h]
0040102C   mov         ecx,10h
00401031   mov         eax,0CCCCCCCCh
00401036   rep stos    dword ptr [edi]
4:        fac(6);
00401038   push        6
0040103A   call        @ILT+5(fac) (0040100a)
0040103F   add         esp,4
5:
6:        return 0;
00401042   xor         eax,eax
7:    }

То есть встраивания не произошло, как я и ожидал

P.S. Быть может, это не такая уж и серьёзная и часто возникающая проблема, но я задался целью прочесть всего Страуструпа, поэтому не хотелось бы, чтобы у меня оставались "белые пятна".

Здравствуйте, Forrest_Gump, Вы писали:

F_G>Бьерн Страуструп "Язык программирования С++" 3-е издание, стр. 186, п. 7.1.1 "Определения функций".
F_G>Сначала приводится пример:

F_G>

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>


#pragma inline_recursion(on)

F_G>inline int fac(int n) {return (n < 2) ? 1 : n * fac(n-1); }

F_G>int main(){
F_G>    fac(6);

F_G>    return 0;
F_G>}
F_G>

[]

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>Каким же будет тогда механизм её вызова ?

Ничто не мешает достаточно умному компилятору "раскрутить" рекурсию в цикл.

Вот пример в VC 7.1

/* main.cpp */ 

#include <iostream>

using namespace std;

/* main() */ 

int fac(int n) { return (n>1)?fac(n-1)*n:1; }

int main()
 {
  cout << "fac(6)=" << fac(6) << endl ;
 
  return 0;
 }

; 13   :   cout << "fac(6)=" << fac(6) << endl ;

    mov    eax, DWORD PTR __imp_?endl@std@@YAAAV?$basic_ostream@DU?$char_traits@D@std@@@1@AAV21@@Z
    push    eax
    push    5
    call    ?fac@@YAHH@Z                ; fac
    mov    edx, DWORD PTR __imp_?cout@std@@3V?$basic_ostream@DU?$char_traits@D@std@@@1@A
    lea    ecx, DWORD PTR [eax+eax*2]
    add    esp, 4
    shl    ecx, 1

Т.е. компилятор встроил один уровень рекурсии.

... << RSDN@Home 1.1.0 stable >>

Любой рекурсивный вызов можно преобразовать в цикл. Другое дело, что такого рода цикл не будет, вероятно, быстрее рекурсии — все равно придется каким-то образом организовывать стек и взаимодействовать с ним на каждой итерации.

Здравствуйте, Forrest_Gump, Вы писали:

F_G>

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

F_G>Поясните, пожалуйста, КАК рекурсивная функция вообще может быть встраиваемой ?
F_G>Каким же будет тогда механизм её вызова ?

Так о том и говорится, что не может. Имеется в виду, что директива 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), где х — целая переменная, а не константа ?

Здравствуйте, 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) <+> F(s(x)))

где <+> — ассоциативная операция, (x <+> (y <+> z)) == ((x <+> y) <+> z)

if(p(x))
  return g(x);

result_t v = h(x);
while(true)
{
  x = s(x);
  if(p(x)) break;
  v <+>= h(x);
}
v <+>= g(x);
return v;

Или, зная нулевое значение для данной операции (у сложения — 0, у умножения — 1, у конкатенации — "")

result_t v = zero;
for(; !p(x); x=s(x))
  v <+>= h(x);

v <+>= g(x);

Левая рекурсия также разворачивается (только вместо v <+>= t() будет v = t() <+> v).

Более сложные случаи с по-прежнему чистой "однополярной" рекурсией также можно развернуть:

F(x) = p01(x) ? g1(x) : p02(x) ? g2(x) : ... p0n(x) ? gn(x)
     : p1(x) ? h1(x)+F(s1(x)) : p2(x) ? .... : hn(x)+F(sn(x))

или, что то же самое,

F(x) = p01(x) ? g1(x) : ... ? p0n(x) : gn(x)
     : (p1(x)?h1(x):...:hn(x)) + F(p1(x)?s1(x):...:sn(x))

     = (p01(x)||...||p0n(x)) ? (p01(x) ? g1(x) : ... : gn(x))
     : (p1(x)?h1(x):...:hn(x)) + F(p1(x)?s1(x):...:sn(x))

     = P0(x) ? G(x) : H(x) + F(S(x))

if(p01(x)) return g1(x);
...
if(p0n(x)) return gn(x);

v = p1(x) ? h1(x) : ... : hn(x);
while(true)
{
  x = p1(x) ? s1(x) : ... : sn(x);

  if(p01(x)) { v += g1(x); break; }
  ...
  if(p0n(x)) { v += gn(x); break; }

  v += p1(x) ? h1(x) : ... : hn(x);
}
return v;

Очевидно, можно сделать так, чтобы каждый предикат вызывался единожды — чуть-чуть развернуть цикл

// первая проверка конца
if(p01(x)) return g1(x);
...
if(p0n(x)) return gn(x);

// первая итерация
if(p1(x)) { v=h1(x); x=s1(x); } else
if(p2(x)) { v=h2(x); x=s2(x); } else
...
          { v=hn(x); x=sn(x); }

while(true)
{
  if(p01(x)) { return v+g1(x); }
  ...
  if(p0n(x)) { return v+gn(x); }

  if(p1(x)) { v+=h1(x); x=s1(x); } else
  if(p2(x)) { v+=h2(x); x=s2(x); } else
  ...
            { v+=hn(x); x=sn(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))) удастся представить в виде бинома (найдя не только коэффициенты, но, возможно, и подходящие операции) — тогда велкам!
А если нет — плачь.

Здравствуйте, jazzer, Вы писали:

F_G>>>Поясните, пожалуйста, КАК рекурсивная функция вообще может быть встраиваемой ?
F_G>>>Каким же будет тогда механизм её вызова ?

А>>Так о том и говорится, что не может. Имеется в виду, что директива inline носит не обязательный характер, а только как рекомендация компилятору.

J>Очень даже может.
J>тоже же хрестоматийный вызов fac(5) может быть преобразован путем встраивания в 5*fac(4), а может и в 5*4*fac(3), а может и до конца вычислить и записать сразу константу куда запрошено.
J>Все зависит от качества компилятора.
Да, есть даже уже классический алгоритм преобразования так называемой хвостовой рекурсии в цикл. Это как раз типичный пример с факториалом сюда подходит. Так что компилятор запросто может для рекурсивной функции генерить цикл, который может развернуть в inline-код.

Здравствуйте, Кодт, Вы писали:

К>По-любому, правая рекурсия без труда превращается в итерацию.
К>

К>F(x) = p(x) ? g(x) : (h(x) <+> F(s(x)))
К>

К>где <+> — ассоциативная операция, (x <+> (y <+> z)) == ((x <+> y) <+> z)
К>[c]
К>if(p(x))
К> return g(x);
и т.д.

Я ещё не разбирался с тем, что ты написал, но если это всё правильно, то я снимаю шляпу

Скажи мне, ГДЕ ты всё это прочёл ?

Здравствуйте, LaptevVV, Вы писали:

L> Да, есть даже уже классический алгоритм преобразования так называемой
L> хвостовой рекурсии в цикл. <...>

Еще проще: часто компиляторы подставляют рекурсивные вызовы на некоторую
глубину (3-4). В результате, скажем рекурсия вложенности 3, требовавшая 3
вызова, будет осуществлена за 1 вызов. Т.е. если функция определена так:

void f()
{
  <pre>
  if(...)
    f();
  <post>
}

То вместо цепочки вызовов:

f();
1.<pre>
  if(...)
    f();
    2.<pre>
      if(...)
        f();
        3.<pre>
          if(...)
            f();
          <post>
      <post>
  <post>

Получится что-то вроде (часть вызовов соптимизируются):

<pre>
if(...)
{
  <pre>
  if(...)
  {
    <pre>
    if(...)
      f();
    <post>
  }
  <post>
}
<post>

Posted via RSDN NNTP Server 1.7 "Bedlam"

Здравствуйте, Павел Кузнецов, Вы писали:

L>> Да, есть даже уже классический алгоритм преобразования так называемой
L>> хвостовой рекурсии в цикл. <...>

ПК>Еще проще: часто компиляторы подставляют рекурсивные вызовы на некоторую
ПК>глубину (3-4). В результате, скажем рекурсия вложенности 3, требовавшая 3
ПК>вызова, будет осуществлена за 1 вызов. Т.е. если функция определена так:
ПК>

ПК>void f()
ПК>{
ПК>  <pre>
ПК>  if(...)
ПК>    f();
ПК>  <post>
ПК>}
ПК>

ПК>То вместо цепочки вызовов:
ПК>

ПК>f();
ПК>1.<pre>
ПК>  if(...)
ПК>    f();
ПК>    2.<pre>
ПК>      if(...)
ПК>        f();
ПК>        3.<pre>
ПК>          if(...)
ПК>            f();
ПК>          <post>
ПК>      <post>
ПК>  <post>
ПК>

ПК>Получится что-то вроде (часть вызовов соптимизируются):
ПК>

ПК>f();
ПК>1.<pre>
ПК>  if(...)
ПК>  {
ПК>    <pre>
ПК>    if(...)
ПК>    {
ПК>      <pre>
ПК>      if(...)
ПК>        f();
ПК>      <post>
ПК>    }
ПК>    <post>
ПК>  }
ПК>  <post>
ПК>

О! Это ж аналог развертки цикла!
А если рекурсия короткая, то она вся и разворачивается!

всюду в предыдущем сообщении я подразумевал, что + и * это произвольные операции, на которые наложено единственное ограничение:

ассоциативность +

ассоциативность *

дистрибутивность слева *(+)
(не помню — нужна в кольце коммутативность или нет; здесь — не нужна).

Известно, что таковы:

арифметические +,* -- кольцо над целыми/вещественными/комплексными числами (а также кольца вычетов по модулю над целыми)

булевы ||,&& -- булева алгебра является субклассом кольца

битовые |,& и ^,& -- соответственно, булева алгебра и кольцо вычетов по модулю 2 в векторном пространстве (целое число как вектор двоичных чисел — разрядов).

Но никто не мешает написать свои функции tipa_plus(lhs,rhs) и tipa_zvezda(lhs,rhs)

(И после этого — кто-то ещё спрашивал, нафига спецразделы высшей математики программисту).

Здравствуйте, Павел Кузнецов, Вы писали:

ПК>Еще проще: часто компиляторы подставляют рекурсивные вызовы на некоторую
ПК>глубину (3-4). В результате, скажем рекурсия вложенности 3, требовавшая 3
ПК>вызова, будет осуществлена за 1 вызов. Т.е. если функция определена так:
В студии это даже можно регулировать
Врубаем встраивание рекурсивных функций
#pragma inline_recursion(on)
Указываем глубину встраивания
#pragma inline_depth(8)

... << RSDN@Home 1.1.3 beta 1 >>

Здравствуйте, Forrest_Gump, Вы писали:

F_G>Скажи мне, ГДЕ ты всё это прочёл ?

Маломало три курса высшей математики, знание корней° и немного эха в голове.

° (Г.Корн, Т.Корн, Справочник по математике, М.: Наука, 1984)

Здравствуйте, Кодт, Вы писали:

К>Здравствуйте, Forrest_Gump, Вы писали:

F_G>>Скажи мне, ГДЕ ты всё это прочёл ?

К>Маломало три курса высшей математики, знание корней° и немного эха в голове.
Что за вуз ? МГУ ? Физтех ?
P.S. Форуму явно нужен тэг [off][/off]

Здравствуйте, Кодт, Вы писали:

К>(не помню — нужна в кольце коммутативность или нет; здесь — не нужна).
Идеалы бывают левыми и правыми: кольцо коммутативно по сложению и не обязательно по умножению.

Здравствуйте, Forrest_Gump, Вы писали:

К>>Маломало три курса высшей математики, знание корней° и немного эха в голове.
F_G>Что за вуз ? МГУ ? Физтех ?
F_G>P.S. Форуму явно нужен тэг [off][/off]

Однако 44 кафедра ЛИАП (ныне СПГУАП)

Здравствуйте, Azir, Вы писали:

A>Здравствуйте, Кодт, Вы писали:

К>>(не помню — нужна в кольце коммутативность или нет; здесь — не нужна).
A>Идеалы бывают левыми и правыми: кольцо коммутативно по сложению и не обязательно по умножению.

Да, спасибо. Я уже в справочник слазил.
В общем, здесь ещё недокольцо: уже две операции, ассоциативность, односторонняя дистрибутивность. Обратимость, кстати, тоже не нужна.

Интересно, для булевых функций какие ещё варианты бывают?

Здравствуйте, 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

... << RSDN@Home 1.1.0 stable >>

	От:	Forrest_Gump
	Дата:	15.02.04 23:12
	Оценка:

	От:	folk
	Дата:	15.02.04 23:22
	Оценка:

	От:	Шахтер
	Дата:	15.02.04 23:58
	Оценка:

	От:	Vamp
	Дата:	16.02.04 07:38
	Оценка:

	От:	Аноним
	Дата:	16.02.04 10:25
	Оценка:

От:	jazzer	Skype: enerjazzer
Дата:	16.02.04 10:30
Оценка:

	От:	Павел Кузнецов
	Дата:	16.02.04 15:52
	Оценка: