Как предотвратить накопление рекурсивного вызова функции (tail-recursion) в стеке? - PullRequest
Новая
       23

Как предотвратить накопление рекурсивного вызова функции (tail-recursion) в стеке?

0 голосов
/ 13 мая 2019

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

Я проверил эту теорию с помощью "gcc" и обнаружил, что вызывающая функцияостается в стеке: 

#include <iostream>

void a(int i)
{
    std::cout << i << std::endl;
    if (i > 0)
        a(i - 1);
    // Also tested return a(i - 1);
}

int main()
{
    a(10);
}

стек вызовов: 

...
a(int i) (/mnt/temp/hackerrank/src/main.cpp:30)
a(int i) (/mnt/temp/hackerrank/src/main.cpp:30)
a(int i) (/mnt/temp/hackerrank/src/main.cpp:30)
main() (/mnt/temp/hackerrank/src/main.cpp:35)

Почему оптимизация не вынуждает всплыть родительский элемент?

Согласно комментариям: эта тема известнадля "Хвостовой рекурсии".

1 Ответ

1 голос
/ 13 мая 2019

Я добавил это в godbolt

На gcc (8.3) и clang (8.0.0) с -O3 оптимизациями, эта функция компилируется в неоперативную функцию.Впечатляет, что это даже верно для MSVC v19.20 с /O2 оптимизациями.

GCC 8.3 / Clang 8.0.0: 

a(int):
        ret

MSVC v19.20 (x64): 

i$ = 8
void a(int) PROC                               ; a, COMDAT
        ret     0
void a(int) ENDP                               ; a

Я также позволил себе сделать пример нетривиальным.Здесь я использую следующий код: 

#include <iostream>

void a(int i)
{
    std::cout << "hello\n";
    if (i > 0)
        a(i - 1);
}

Вывод компилятора для этого с gcc trunc с включенной оптимизацией -O3 следующий: 

.LC0:
        .string "hello\n"
a(int):
        push    rbx
        mov     ebx, edi
        jmp     .L3
.L6:
        sub     ebx, 1
.L3:
        mov     edx, 6
        mov     esi, OFFSET FLAT:.LC0
        mov     edi, OFFSET FLAT:_ZSt4cout
        call    std::basic_ostream<char, std::char_traits<char> >& std::__ostream_insert<char, std::char_traits<char> >(std::basic_ostream<char, std::char_traits<char> >&, char const*, long)
        test    ebx, ebx
        jg      .L6
        pop     rbx
        ret
_GLOBAL__sub_I_a(int):
        sub     rsp, 8
        mov     edi, OFFSET FLAT:_ZStL8__ioinit
        call    std::ios_base::Init::Init() [complete object constructor]
        mov     edx, OFFSET FLAT:__dso_handle
        mov     esi, OFFSET FLAT:_ZStL8__ioinit
        mov     edi, OFFSET FLAT:_ZNSt8ios_base4InitD1Ev
        add     rsp, 8
        jmp     __cxa_atexit

Из тщательного изученияединственная инструкция call - это метод io для записи сообщения на каждой итерации.Затем выполняется test (оператор if).Если i > 0, управление подскакивает вверх, уменьшается на i и делает все это снова.Другая ветвь оператора if (ложный случай) просто возвращает (после очистки стека).

Таким образом, нет накопления кадров стека даже в этом нетривиальном примере.Это выполняется с помощью инструкции jmp, потому что (как вы сказали) информация о предыдущем выполнении не имеет значения.

...