Что такое хвостовая рекурсия?

Question

Пока я начинал изучать шепот, я встретил термин хвост-рекурсив . Что это значит точно?

Answer 1

Существует два основных вида рекурсии: рекурсия головы и рекурсия хвоста.

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

В хвостовой рекурсивной функции все вычисления выполняются первыми и рекурсивный вызов - это последнее, что происходит.

Взято из этого супер-классного поста. Пожалуйста, подумайте над прочтением.

Answer 2

Рекурсия означает функцию, вызывающую себя. Например:

(define (un-ended name)
  (un-ended 'me)
  (print "How can I get here?"))

Tail-Recursion означает рекурсию, завершающую функцию:

(define (un-ended name)
  (print "hello")
  (un-ended 'me))

Видите, последнее, что делает незавершенная функция (процедура, на языке жаргона Scheme), - это вызывает себя. Другой (более полезный) пример:

(define (map lst op)
  (define (helper done left)
    (if (nil? left)
        done
        (helper (cons (op (car left))
                      done)
                (cdr left))))
  (reverse (helper '() lst)))

В вспомогательной процедуре последнее, что она делает, если левая часть не равна нулю, - это вызывает себя (ПОСЛЕ того, что что-то минует и что-то cdr). Это в основном то, как вы отображаете список.

Хвостовая рекурсия имеет большое преимущество, заключающееся в том, что интерпретатор (или компилятор, зависящий от языка и поставщика) может оптимизировать его и преобразовать в нечто, эквивалентное циклу while. На самом деле, в традиции Scheme большинство циклов for и while выполняется методом хвостовой рекурсии (насколько я знаю, для for и while нет).

Answer 3

На этот вопрос есть много хороших ответов ... но я не могу не согласиться с альтернативным подходом к определению "рекурсии хвоста" или, по крайней мере, "правильной рекурсии хвоста". А именно: следует ли рассматривать его как свойство определенного выражения в программе? Или следует рассматривать его как свойство реализации языка программирования ?

Более подробно о последнем представлении есть классическая бумага Уилла Клингера «Правильная рекурсия хвоста и эффективность пространства» (PLDI 1998), в которой «правильная рекурсия хвоста» определяется как свойство Реализация языка программирования. Определение построено таким образом, чтобы можно было игнорировать детали реализации (например, представлен ли стек вызовов на самом деле через стек времени выполнения или через выделенный в куче связанный список кадров).

Для достижения этой цели используется асимптотический анализ: не времени выполнения программы, как обычно видят, а скорее программы использования пространства . Таким образом, использование пространства распределенного списка, выделенного в куче, по сравнению со стеком вызовов времени выполнения оказывается асимптотически эквивалентным; таким образом, можно игнорировать эту деталь реализации языка программирования (деталь, которая, безусловно, имеет большое значение на практике, но может немного испачкать воду, когда кто-то пытается определить, удовлетворяет ли данная реализация требованию «рекурсивности хвоста свойства»). )

Статья заслуживает тщательного изучения по ряду причин:

• Это дает индуктивное определение хвостовых выражений и хвостовых вызовов программы. (Такое определение и почему такие призывы важны, по-видимому, является предметом большинства других ответов, приведенных здесь.)

  Вот эти определения, просто чтобы дать представление о тексте:

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

  1. Тело лямбда-выражения является хвостовым выражением
  2. Если (if E0 E1 E2) является хвостовым выражением, то и E1 и E2 являются хвостовыми выражениями.
  3. Ничто другое не является выражением хвоста.

  Определение 2 A хвостовой вызов - это хвостовое выражение, которое является вызовом процедуры.

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

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

  Например, после предоставления определений для машин с соответственно: 1. управлением памятью на основе стека, 2. сборкой мусора, но без хвостовых вызовов, 3. сборкой мусора и хвостовыми вызовами, документ продолжает работу с еще более продвинутыми стратегиями управления хранением , например 4. «evlis tail recursion», где не требуется сохранять среду при оценке последнего аргумента подвыражения в хвостовом вызове, 5. сокращать среду замыкания до just свободные переменные этого замыкания и 6. так называемая семантика «безопасного пространства», как определено Appel и Shao .

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

---

(Читая мой ответ сейчас, я не уверен, смог ли я действительно зафиксировать критические моменты статьи Клингера . Но, увы, я не могу посвятить больше времени разработке этого ответа прямо сейчас.)

Answer 4

Рекурсивная функция - это функция, которую вызывает сама по себе

Это позволяет программистам писать эффективные программы, используя минимальный объем кода .

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

Я объясню как Простая рекурсивная функция, так и хвостовая рекурсивная функция

Для того, чтобы написать Простая рекурсивная функция

1. Первое, на что нужно обратить внимание, это когда вы решите выйти цикла, который является циклом if
2. Во-вторых, что делать, если мы являемся нашей собственной функцией

Из приведенного примера:

public static int fact(int n){
  if(n <=1)
     return 1;
  else 
     return n * fact(n-1);
}

Из приведенного выше примера

if(n <=1)
     return 1;

Является решающим фактором при выходе из цикла

else 
     return n * fact(n-1);

Фактическая обработка, которая должна быть сделана

Позвольте мне разбить задание по одному для простоты понимания.

Давайте посмотрим, что произойдет внутри, если я бегу fact(4)

1. Подставляя n = 4

public static int fact(4){
  if(4 <=1)
     return 1;
  else 
     return 4 * fact(4-1);
}

If цикл завершается ошибкой, поэтому он переходит в else цикл так что возвращается 4 * fact(3)

2. В стековой памяти у нас есть 4 * fact(3)

   Подставляя n = 3

public static int fact(3){
  if(3 <=1)
     return 1;
  else 
     return 3 * fact(3-1);
}

If цикл завершается ошибкой, поэтому он переходит к else цикл

, поэтому возвращается 3 * fact(2)

Помните, мы назвали `` `4 * fact (3)` `

Выход для fact(3) = 3 * fact(2)

Пока в стеке 4 * fact(3) = 4 * 3 * fact(2)

3. В стековой памяти у нас есть 4 * 3 * fact(2)

   Подставляя n = 2

public static int fact(2){
  if(2 <=1)
     return 1;
  else 
     return 2 * fact(2-1);
}

If цикл завершается ошибкой, поэтому он переходит к else цикл

поэтому возвращается 2 * fact(1)

Помните, мы звонили 4 * 3 * fact(2)

Выход для fact(2) = 2 * fact(1)

Пока в стеке есть 4 * 3 * fact(2) = 4 * 3 * 2 * fact(1)

3. В стековой памяти у нас есть 4 * 3 * 2 * fact(1)

   Подставляя n = 1

public static int fact(1){
  if(1 <=1)
     return 1;
  else 
     return 1 * fact(1-1);
}

If петля верна

так что возвращает 1

Помните, мы звонили 4 * 3 * 2 * fact(1)

Выход для fact(1) = 1

Пока в стеке есть 4 * 3 * 2 * fact(1) = 4 * 3 * 2 * 1

Наконец, результат fact (4) = 4 * 3 * 2 * 1 = 24

Хвостовая рекурсия будет

public static int fact(x, running_total=1) {
    if (x==1) {
        return running_total;
    } else {
        return fact(x-1, running_total*x);
    }
}

1. Подставляя n = 4

public static int fact(4, running_total=1) {
    if (x==1) {
        return running_total;
    } else {
        return fact(4-1, running_total*4);
    }
}

If цикл завершается ошибкой, поэтому он переходит к else цикл поэтому он возвращает fact(3, 4)

2. В стековой памяти у нас есть fact(3, 4)

   Подставляя n = 3

public static int fact(3, running_total=4) {
    if (x==1) {
        return running_total;
    } else {
        return fact(3-1, 4*3);
    }
}

If цикл завершается ошибкой, поэтому он переходит к else цикл

так что возвращает fact(2, 12)

2. В стековой памяти у нас есть fact(2, 12)

   Подставляя n = 2

public static int fact(2, running_total=12) {
    if (x==1) {
        return running_total;
    } else {
        return fact(2-1, 12*2);
    }
}

If цикл завершается ошибкой, поэтому он переходит к else цикл

так что возвращается fact(1, 24)

3. В стековой памяти у нас есть fact(1, 24)

   Подставляя n = 1

public static int fact(1, running_total=24) {
    if (x==1) {
        return running_total;
    } else {
        return fact(1-1, 24*1);
    }
}

If петля верна

так что возвращает running_total

Выход для running_total = 24

Наконец, результат факт (4,1) = 24

Answer 5

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

def recursiveFunction(some_params):
    # some code here
    return recursiveFunction(some_args)
    # no code after the return statement

Компиляторы и интерпретаторы, которые реализуют оптимизацию хвостовых вызовов или устранение хвостовых вызовов , могут оптимизировать рекурсивный код для предотвращения переполнения стека. Если ваш компилятор или интерпретатор не реализует оптимизацию хвостовых вызовов (например, интерпретатор CPython), то нет никакой дополнительной выгоды в написании вашего кода таким образом.

Например, это стандартная рекурсивная факториальная функция в Python:

def factorial(number):
    if number == 1:
        # BASE CASE
        return 1
    else:
        # RECURSIVE CASE
        # Note that `number *` happens *after* the recursive call.
        # This means that this is *not* tail call recursion.
        return number * factorial(number - 1)

И это рекурсивная версия хвостового вызова факториальной функции:

def factorial(number, accumulator=1):
    if number == 0:
        # BASE CASE
        return accumulator
    else:
        # RECURSIVE CASE
        # There's no code after the recursive call.
        # This is tail call recursion:
        return factorial(number - 1, number * accumulator)
print(factorial(5))

(Обратите внимание, что, хотя это код Python, интерпретатор CPython не выполняет оптимизацию хвостовых вызовов, поэтому такая организация кода не дает никаких преимуществ во время выполнения.)

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

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

Переполнения стека возникают, когда в стеке вызовов слишком много объектов кадра. Объект кадра помещается в стек вызовов при вызове функции и извлекается из стека вызовов при возврате функции. Объекты фрейма содержат информацию, такую ​​как локальные переменные и строку кода, к которой нужно вернуться при возврате функции.

Если ваша рекурсивная функция делает слишком много рекурсивных вызовов без возврата, стек вызовов может превысить свой предел объекта фрейма. (Число зависит от платформы; в Python по умолчанию это 1000 кадровых объектов.) Это вызывает ошибку переполнение стека . (Эй, отсюда и название этого сайта!)

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

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

Answer 6

Многие люди уже объясняли рекурсию здесь. Я хотел бы привести пару соображений о некоторых преимуществах рекурсии из книги Риккардо Террелла «Параллелизм в .NET, Современные шаблоны параллельного и параллельного программирования»:

«Функциональная рекурсия - это естественный способ итерации в FP, потому что она избегает мутации состояния. Во время каждой итерации передается новое значение в конструктор цикла вместо того, чтобы обновляться (мутировать). В Кроме того, рекурсивная функция может быть составлена, делая вашу программу более модульный, а также введение возможностей для эксплуатации распараллеливание. "

Вот также некоторые интересные заметки из той же книги о хвостовой рекурсии:

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

ПРИМЕЧАНИЕ. Основной причиной для хвостового вызова в качестве оптимизации является улучшить локальность данных, использование памяти и кэш-памяти. Делая хвост вызов, вызываемый использует то же пространство стека, что и вызывающий. Это уменьшает давление памяти. Это незначительно улучшает кэш, потому что тот же память используется для последующих абонентов и может оставаться в кеше, вместо удаления старой строки кэша, чтобы освободить место для нового кэша линия.