Рекурсия хвоста в C ++

Может ли кто-нибудь показать мне простую хвостовую рекурсивную функцию в C ++?

Почему хвостовая recursion лучше, если она даже есть?

Какие еще виды рекурсии существуют, кроме рекурсии хвоста?

    6 Solutions collect form web for “Рекурсия хвоста в C ++”

    Простая хвостовая рекурсивная функция:

     unsigned int f( unsigned int a ) { if ( a == 0 ) { return a; } return f( a - 1 ); // tail recursion } 

    Рекурсия хвоста – это в основном, когда:

    • существует только один рекурсивный вызов
    • этот вызов является последним утверждением функции

    И это не «лучше», за исключением того, что хороший компилятор может удалить рекурсию, превратив ее в цикл. Это может быть быстрее и, безусловно, будет экономить на использовании стека. Компилятор GCC может сделать эту оптимизацию.

    Откат хвоста в C ++ выглядит так же, как C или любой другой язык.

     void countdown( int count ) { if ( count ) return countdown( count - 1 ); } 

    Рекурсия хвоста (и вызов хвоста в целом) требует очистки кадра стека вызывающего абонента перед выполнением хвостового вызова. Для программиста хвостовая recursion похожа на цикл, при этом return сводится к работе как goto first_line; , Однако компилятор должен определить, что вы делаете, и если этого не произойдет, все равно будет добавлен дополнительный стек кадров. Большинство компиляторов поддерживают его, но писать цикл или goto обычно проще и менее рискованно.

    Нерекурсивные хвостовые вызовы могут включать случайное разветвление (например, goto к первой строке какой-либо другой функции), что является более уникальным средством.

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

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

     int factorial( int n, int acc = 1 ) { if ( n == 0 ) return acc; else return factorial( n-1, acc * n ); } 

    Рекурсия хвоста является особым случаем хвостового вызова. Хвост вызова – это то, где компилятор может видеть, что нет никаких операций, которые необходимо выполнить при возврате из вызываемой функции – по существу, превращения возврата вызываемой функции в нее. Компилятор часто может выполнять несколько операций исправления стека, а затем переходить (а не звонить) на адрес первой команды вызываемой функции .

    Одна из замечательных вещей в этом, кроме устранения некоторых обратных вызовов, заключается в том, что вы также сокращаете использование стека. На некоторых платформах или в коде ОС стеки могут быть весьма ограниченными, а на современных компьютерах, таких как процессоры x86 на наших настольных компьютерах, уменьшает использование стека, что улучшит производительность кэша данных.

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

    Ниже показан общий способ сделать рекурсивный вызов, который будет сложнее для компилятора превратиться в цикл:

     int sum(int a[], unsigned len) { if (len==0) { return 0; } return a[0] + sum(a+1,len-1); } 

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

    Если вы это сделали:

     static int sum_helper(int acc, unsigned len, int a[]) { if (len == 0) { return acc; } return sum_helper(acc+a[0], len-1, a+1); } int sum(int a[], unsigned len) { return sum_helper(0, len, a); } 

    Вы могли бы использовать вызовы в обеих функциях, являющихся хвостовыми вызовами. Здесь основное задание функции суммы – это перемещение значения и очистка позиции регистра или стека. Sum_helper выполняет всю математику.

    Поскольку вы упомянули о C ++ в своем вопросе, я расскажу о некоторых особых вещах. C ++ скрывает от вас некоторые вещи, которых нет. Из этих деструкторов главное, что будет мешать оптимизации хвостового вызова.

     int boo(yin * x, yang *y) { dharma z = x->foo() + y->bar(); return z.baz(); } 

    В этом примере вызов baz на самом деле не является хвостовым вызовом, так как z следует уничтожить после возврата из baz. Я считаю, что правила C ++ могут затруднить оптимизацию даже в тех случаях, когда переменная не нужна для продолжительности вызова, например:

     int boo(yin * x, yang *y) { dharma z = x->foo() + y->bar(); int u = z.baz(); return qwerty(u); } 

    z, возможно, придется разрушить после возвращения из qwerty здесь.

    Другое дело было бы неявное преобразование типов, которое также может происходить и в C, но может быть более сложным и распространенным в C ++. Например:

     static double sum_helper(double acc, unsigned len, double a[]) { if (len == 0) { return acc; } return sum_helper(acc+a[0], len-1, a+1); } int sum(double a[], unsigned len) { return sum_helper(0.0, len, a); } 

    Здесь вызов sum_helper не является хвостовым вызовом, потому что sum_helper возвращает double, и сумма должна будет преобразовать его в int.

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

     bool write_it(int it) { return cout < < it; } 

    Здесь есть вызов, сделанный cout.operator < < как последнее утверждение. cout вернет ссылку на себя (вот почему вы можете объединить множество вещей в список, разделенный <<), который затем принудительно оценивается как bool, который в конечном итоге вызывает другой метод cout, operator bool ( ). Этот cout.operator bool () можно было бы назвать хвостовым вызовом в этом случае, но оператор << не смог.

    РЕДАКТИРОВАТЬ:

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

    Рекурсия хвоста на самом деле не существует на уровне компилятора в C ++.

    Хотя вы можете писать программы, в которых используется recursion хвоста, вы не получаете наследуемых преимуществ хвостовой рекурсии, реализованных путем поддержки компиляторов / интерпретаторов / языков. Например, схема поддерживает оптимизацию хвостовой рекурсии, так что она в основном изменит рекурсию на итерацию. Это делает его более быстрым и неуязвимым для переполнения стека. У C ++ такого нет. (наименее не компилятор, который я видел)

    По-видимому, оптимизация хвостовой рекурсии существует как в MSVC ++, так и в GCC. См. Этот вопрос для деталей.

    В Википедии есть достойная статья о рекурсии хвоста . В принципе, recursion хвоста лучше, чем регулярная recursion, потому что тривиально оптимизировать ее в итеративном цикле, а итеративные петли обычно более эффективны, чем рекурсивные вызовы функций. Это особенно важно на функциональных языках, где у вас нет циклов.

    Для C ++ все равно хорошо, если вы можете написать рекурсивные циклы с хвостовой рекурсией, так как они могут быть оптимизированы, но в таких случаях вы можете просто сделать это итеративно в первую очередь, так что выигрыш не так велик, как если бы он быть на функциональном языке.

    Рекурсия хвоста – это трюк, позволяющий одновременно справляться с двумя проблемами. Первый выполняет цикл, когда трудно узнать количество итераций.

    Хотя это можно проработать с простой рекурсией, возникает вторая проблема, которая связана с переполнением стека из-за того, что рекурсивный вызов выполняется слишком много раз. Хвост-вызов – это решение, когда оно сопровождается «вычислением и переносом».

    В базовом CS вы узнаете, что компьютерный алгоритм должен иметь инвариант и условие завершения. Это база для построения хвостовой рекурсии.

    1. Все вычисления происходят при передаче аргументов.
    2. Все результаты должны быть переданы на вызовы функций.
    3. Хвост вызова является последним вызовом и происходит при завершении.

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

    Возьмем, например, вычисление степени 10, которая тривиальна и может быть записана петлей.

    Должен выглядеть примерно так

     template T pow10(T const p, T const res =1) { return p ? res: pow10(--p,10*res); } 

    Это дает выполнение, например, 4:

    RET, р, разреш

    -, 4,1

    -, 3,10

    -, 2100

    -, 1,1000

    -, 0,10000

    10000, -, –

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

    Рекурсия хвоста очень важна, поскольку она может обеспечить готовые оценки времени компиляции, например, вышеизложенное может быть сделано.

     template struct powc10 { int operator()() const { return powc10()(); } }; template struct powc10<0,R> { int operator()() const { return R; } }; 

    это можно использовать как powc10<10>()() для вычисления 10-й мощности во время компиляции.

    Большинство компиляторов имеют ограничение на вложенные вызовы, поэтому помогает трюк с хвостом. Очевидно, что нет циклов метапрограмм, поэтому нужно использовать рекурсию.

    Давайте будем гением компьютера.