Вопрос:

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

algorithm language-agnostic functional-programming recursion tail-recursion

362720 просмотра

26 ответа

1108 Репутация автора

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

Автор: Ben Lever Источник Размещён: 29.08.2008 03:48

Ответы (26)


8 плюса

163360 Репутация автора

Я не программист на Лиспе, но думаю, это поможет.

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

Автор: Matt Hamilton Размещён: 29.08.2008 03:50

62 плюса

113812 Репутация автора

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

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

В основном рекурсии Tail могут быть оптимизированы в итерацию.

Автор: FlySwat Размещён: 29.08.2008 03:55

28 плюса

21186 Репутация автора

Хвостовая рекурсия относится к рекурсивному вызову, который является последним в последней логической инструкции в рекурсивном алгоритме.

Обычно в рекурсии у вас есть базовый случай, который останавливает рекурсивные вызовы и начинает выталкивать стек вызовов. Чтобы использовать классический пример, хотя и больше C-ish, чем Lisp, функция факториала иллюстрирует хвостовую рекурсию. Рекурсивный вызов происходит после проверки условия базового случая.

factorial(x, fac) {
  if (x == 1)
     return fac;
   else
     return factorial(x-1, x*fac);
}

Обратите внимание, что первоначальный вызов факториала должен быть факториалом (n, 1), где n - это число, для которого нужно рассчитать факториал.

Автор: Peter Meyer Размещён: 29.08.2008 03:57

600 плюса

0 Репутация автора

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

В хвостовой рекурсии вы сначала выполняете свои вычисления, а затем выполняете рекурсивный вызов, передавая результаты вашего текущего шага следующему рекурсивному шагу. Это приводит к тому, что последнее утверждение находится в форме (return (recursive-function params)). По сути, возвращаемое значение любого заданного рекурсивного шага совпадает с возвращаемым значением следующего рекурсивного вызова .

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

Автор: user316 Размещён: 29.08.2008 03:57

61 плюса

59019 Репутация автора

Вместо объяснения словами, вот пример. Это версия Scheme факториальной функции:

(define (factorial x)
  (if (= x 0) 1
      (* x (factorial (- x 1)))))

Вот версия факториала с хвостовой рекурсией:

(define factorial
  (letrec ((fact (lambda (x accum)
                   (if (= x 0) accum
                       (fact (- x 1) (* accum x))))))
    (lambda (x)
      (fact x 1))))

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

Автор: Kyle Cronin Размещён: 29.08.2008 03:57

60 плюса

28495 Репутация автора

В файле жаргона есть это, чтобы сказать об определении хвостовой рекурсии:

хвостовая рекурсия /n./

Если вы уже не устали от этого, посмотрите хвостовую рекурсию.

Автор: Pat Размещён: 29.08.2008 07:21

124 плюса

7456 Репутация автора

Этот отрывок из книги « Программирование на Lua» показывает, как сделать правильную рекурсию хвоста (на Lua, но должна также применяться к Lisp) и почему это лучше.

Хвост вызова [хвост рекурсии] является своего рода Goto , одетый , как вызов. Хвостовой вызов происходит, когда функция вызывает другое как последнее действие, так что ей больше нечего делать. Например, в следующем коде вызов gявляется хвостовым вызовом:

function f (x)
  return g(x)
end

После fзвонков gбольше делать нечего. В таких ситуациях программе не нужно возвращаться к вызывающей функции после завершения вызываемой функции. Следовательно, после хвостового вызова программе не нужно хранить какую-либо информацию о вызывающей функции в стеке. ...

Поскольку правильный хвостовой вызов не использует пространство стека, не существует ограничения на число «вложенных» хвостовых вызовов, которые может выполнить программа. Например, мы можем вызвать следующую функцию с любым числом в качестве аргумента; он никогда не переполнит стек:

function foo (n)
  if n > 0 then return foo(n - 1) end
end

... Как я уже говорил ранее, хвостовой вызов - это своего рода goto. Как таковое, довольно полезное применение правильных хвостовых вызовов в Lua для программирования конечных автоматов. Такие приложения могут представлять каждое состояние функцией; изменить состояние означает перейти (или вызвать) определенную функцию. В качестве примера рассмотрим простую игру-лабиринт. В лабиринте есть несколько комнат, каждая из которых имеет до четырех дверей: север, юг, восток и запад. На каждом шаге пользователь вводит направление движения. Если в этом направлении есть дверь, пользователь идет в соответствующую комнату; в противном случае программа выводит предупреждение. Цель состоит в том, чтобы перейти из начальной комнаты в последнюю комнату.

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

function room1 ()
  local move = io.read()
  if move == "south" then return room3()
  elseif move == "east" then return room2()
  else print("invalid move")
       return room1()   -- stay in the same room
  end
end

function room2 ()
  local move = io.read()
  if move == "south" then return room4()
  elseif move == "west" then return room1()
  else print("invalid move")
       return room2()
  end
end

function room3 ()
  local move = io.read()
  if move == "north" then return room1()
  elseif move == "east" then return room4()
  else print("invalid move")
       return room3()
  end
end

function room4 ()
  print("congratulations!")
end

Итак, вы видите, когда вы делаете рекурсивный вызов вроде:

function x(n)
  if n==0 then return 0
  n= n-2
  return x(n) + 1
end

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

Автор: Hoffmann Размещён: 29.08.2008 04:03

177 плюса

39455 Репутация автора

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

while(E) { S }; return Q

где Eи Qявляются выражениями и Sпредставляет собой последовательность операторов, и превращают ее в хвостовую рекурсивную функцию

f() = if E then { S; return f() } else { return Q }

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

sum(n) {
  int i = 1, k = 0;
  while( i <= n ) {
    k += i;
    ++i;
  }
  return k;
}

эквивалентно хвостовой рекурсивной функции

sum_aux(n,i,k) {
  if( i <= n ) {
    return sum_aux(n,i+1,k+i);
  } else {
    return k;
  }
}

sum(n) {
  return sum_aux(n,1,0);
}

(Это «обертывание» хвостовой рекурсивной функции с функцией с меньшим количеством параметров является обычной функциональной идиомой.)

Автор: Chris Conway Размещён: 31.08.2008 05:29

1418 плюса

34480 Репутация автора

Решение

Рассмотрим простую функцию, которая добавляет первые N целых чисел. (например sum(5) = 1 + 2 + 3 + 4 + 5 = 15).

Вот простая реализация JavaScript, которая использует рекурсию:

function recsum(x) {
    if (x===1) {
        return x;
    } else {
        return x + recsum(x-1);
    }
}

Если бы вы позвонили recsum(5), это то, что интерпретатор JavaScript будет оценивать:

recsum(5)
5 + recsum(4)
5 + (4 + recsum(3))
5 + (4 + (3 + recsum(2)))
5 + (4 + (3 + (2 + recsum(1))))
5 + (4 + (3 + (2 + 1)))
15

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

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

function tailrecsum(x, running_total=0) {
    if (x===0) {
        return running_total;
    } else {
        return tailrecsum(x-1, running_total+x);
    }
}

Вот последовательность событий, которые произошли бы, если бы вы вызвали tailrecsum(5)(что будет эффективно tailrecsum(5, 0)из-за второго аргумента по умолчанию).

tailrecsum(5, 0)
tailrecsum(4, 5)
tailrecsum(3, 9)
tailrecsum(2, 12)
tailrecsum(1, 14)
tailrecsum(0, 15)
15

В случае хвостовой рекурсии, с каждой оценкой рекурсивного вызова, running_totalобновляется.

Примечание: в оригинальном ответе использованы примеры из Python. Они были изменены на JavaScript, поскольку современные интерпретаторы JavaScript поддерживают оптимизацию хвостовых вызовов, а интерпретаторы Python - нет.

Автор: Lorin Hochstein Размещён: 31.08.2008 06:21

25 плюса

11056 Репутация автора

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

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

Автор: Chris Smith Размещён: 31.08.2008 11:52

4 плюса

187 Репутация автора

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

(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)))

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

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

Автор: magice Размещён: 02.09.2008 02:08

8 плюса

25052 Репутация автора

Вот версия Perl 5 tailrecsumфункции, упомянутой ранее.

sub tail_rec_sum($;$){
  my( $x,$running_total ) = (@_,0);

  return $running_total unless $x;

  @_ = ($x-1,$running_total+$x);
  goto &tail_rec_sum; # throw away current stack frame
}
Автор: Brad Gilbert Размещён: 01.10.2008 10:06

11 плюса

400 Репутация автора

В Java возможна хвостовая рекурсивная реализация функции Фибоначчи:

public int tailRecursive(final int n) {
    if (n <= 2)
        return 1;
    return tailRecursiveAux(n, 1, 1);
}

private int tailRecursiveAux(int n, int iter, int acc) {
    if (iter == n)
        return acc;
    return tailRecursiveAux(n, ++iter, acc + iter);
}

Сравните это со стандартной рекурсивной реализацией:

public int recursive(final int n) {
    if (n <= 2)
        return 1;
    return recursive(n - 1) + recursive(n - 2);
}
Автор: jorgetown Размещён: 14.10.2008 09:20

17 плюса

1151 Репутация автора

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

Очень просто и интуитивно понятно.

Простой способ определить, является ли рекурсивная функция хвостовой рекурсивной, если она возвращает конкретное значение в базовом случае. Это означает, что он не возвращает 1 или true или что-то подобное. Скорее всего, он вернет какой-то вариант одного из параметров метода.

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

public static int factorial(int mynumber) {
    if (mynumber == 1) {
        return 1;
    } else {            
        return mynumber * factorial(--mynumber);
    }
}

public static int tail_factorial(int mynumber, int sofar) {
    if (mynumber == 1) {
        return sofar;
    } else {
        return tail_factorial(--mynumber, sofar * mynumber);
    }
}
Автор: AbuZubair Размещён: 19.12.2010 03:52

10 плюса

0 Репутация автора

Вот пример Common Lisp, который выполняет факториалы с использованием хвостовой рекурсии. Из-за отсутствия стека, можно выполнять безумно большие факторные вычисления ...

(defun ! (n &optional (product 1))
    (if (zerop n) product
        (! (1- n) (* product n))))

А потом для удовольствия вы можете попробовать (format nil "~R" (! 25))

Автор: user922475 Размещён: 11.03.2012 06:07

5 плюса

1735 Репутация автора

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

Вот статья с некоторыми примерами в C #, F # и C ++ \ CLI: Приключения в Tail Recursion в C #, F # и C ++ \ CLI .

C # не оптимизирует для рекурсии хвостового вызова, тогда как F # делает.

Принципиальные различия включают в себя циклы против лямбда-исчисления. C # разработан с учетом циклов, тогда как F # построен на принципах лямбда-исчисления. За очень хорошую (и бесплатную) книгу о принципах лямбда-исчисления см. « Структура и интерпретация компьютерных программ» Абельсона, Суссмана и Суссмана .

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

Если вы хотите прочитать о некоторых конструктивных различиях рекурсии хвостового вызова между C # и F #, см. Генерация кода операции Tail-Call в C # и F # .

Если вам нужно знать, какие условия мешают компилятору C # выполнять оптимизацию хвостового вызова, см. Эту статью: Условия хвостового вызова JIT CLR .

Автор: devinbost Размещён: 28.04.2014 07:13

14 плюса

1263 Репутация автора

Лучший способ для меня понять tail call recursion- это особый случай рекурсии, когда последний вызов (или хвостовой вызов) - это сама функция.

Сравнение примеров, представленных в Python:

def recsum(x):
 if x == 1:
  return x
 else:
  return x + recsum(x - 1)

^ RECURSION

def tailrecsum(x, running_total=0):
  if x == 0:
    return running_total
  else:
    return tailrecsum(x - 1, running_total + x)

^ ХВОСТ РЕКУРСИЯ

Как вы можете видеть , в общем рекурсивной версии, окончательный вызов в блоке кода является x + recsum(x - 1). Таким образом, после вызова recsumметода есть еще одна операция x + ...

Однако в хвостовой рекурсивной версии последний вызов (или хвостовой вызов) в блоке кода tailrecsum(x - 1, running_total + x)означает, что последний вызов сделан самому методу, и после этого не выполняется никаких операций.

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

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

NB. Помните, что приведенный выше пример написан на языке Python, среда выполнения которого не поддерживает TCO. Это всего лишь пример, чтобы объяснить суть. TCO поддерживается на таких языках, как Scheme, Haskell и т. Д.

Автор: Abhiroop Sarkar Размещён: 21.12.2015 11:47

7 плюса

2173 Репутация автора

Это выдержка из структуры и интерпретации компьютерных программ о хвостовой рекурсии.

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

Одна из причин того, что различие между процессом и процедурой может сбивать с толку, заключается в том, что большинство реализаций общих языков (включая Ada, Pascal и C) спроектированы таким образом, что интерпретация любой рекурсивной процедуры потребляет объем памяти, который увеличивается с ростом число вызовов процедур, даже если описанный процесс в принципе является итеративным. Как следствие, эти языки могут описывать итеративные процессы, только прибегая к специальным «циклическим конструкциям», таким как do, repeat, before, for и while. Реализация Схемы не разделяет этот недостаток. Он будет выполнять итеративный процесс в постоянном пространстве, даже если итерационный процесс описывается рекурсивной процедурой. Реализация с этим свойством называется хвостовой рекурсией. В хвостовой рекурсивной реализации итерация может быть выражена с использованием обычного механизма вызова процедур, так что специальные итерационные конструкции полезны только как синтаксический сахар.

Автор: ayushgp Размещён: 27.06.2016 09:41

9 плюса

2854 Репутация автора

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

Так что это хвостовая рекурсия, т. Е. N (x - 1, p * x) - последний оператор в функции, где компилятор умен, чтобы выяснить, что его можно оптимизировать для цикла for (factorial). Второй параметр p несет значение промежуточного продукта.

function N(x, p) {
   return x == 1 ? p : N(x - 1, p * x);
}

Это нерекурсивный способ написания вышеупомянутой факториальной функции (хотя некоторые компиляторы C ++ в любом случае могут ее оптимизировать).

function N(x) {
   return x == 1 ? 1 : x * N(x - 1);
}

но это не так

function F(x) {
  if (x == 1) return 0;
  if (x == 2) return 1;
  return F(x - 1) + F(x - 2);
}

Я написал длинный пост под названием « Понимание рекурсии хвоста - Visual Studio C ++ - представление сборки »

введите описание изображения здесь

Автор: justyy Размещён: 08.11.2016 11:21

6 плюса

69952 Репутация автора

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

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

Автор: user633183 Размещён: 23.12.2016 06:04

3 плюса

2793 Репутация автора

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

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

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

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

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

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

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

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

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

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

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

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

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


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

Автор: pnkfelix Размещён: 05.07.2017 10:51

5 плюса

358 Репутация автора

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

Рассмотрим проблему вычисления факториала числа.

Прямой подход будет:

  factorial(n):

    if n==0 then 1

    else n*factorial(n-1)

Предположим, вы звоните факториал (4). Дерево рекурсии будет:

       factorial(4)
       /        \
      4      factorial(3)
     /             \
    3          factorial(2)
   /                  \
  2                factorial(1)
 /                       \
1                       factorial(0)
                            \
                             1    

Максимальная глубина рекурсии в указанном выше случае составляет O (n).

Однако рассмотрим следующий пример:

factAux(m,n):
if n==0  then m;
else     factAux(m*n,n-1);

factTail(n):
   return factAux(1,n);

Дерево рекурсии для factTail (4) будет:

factTail(4)
   |
factAux(1,4)
   |
factAux(4,3)
   |
factAux(12,2)
   |
factAux(24,1)
   |
factAux(24,0)
   |
  24

Здесь также максимальная глубина рекурсии равна O (n), но ни один из вызовов не добавляет никакой дополнительной переменной в стек. Следовательно, компилятор может покончить со стеком.

Автор: coding_ninza Размещён: 23.12.2017 12:26

4 плюса

5469 Репутация автора

Есть два основных вида рекурсии: голова рекурсии и хвост рекурсии.

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

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

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

Автор: Abdullah Khan Размещён: 08.05.2018 10:09

1 плюс

63 Репутация автора

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

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

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

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

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

Автор: Vadim S. Размещён: 04.01.2019 09:19

0 плюса

139 Репутация автора

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

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

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

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

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

  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)

  1. В стековой памяти мы имеем 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)

  1. В стековой памяти мы имеем 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)

  1. В стековой памяти мы имеем 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

Результат по факту (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)

  1. В стековой памяти мы имеем 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)

  1. В стековой памяти мы имеем 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)

  1. В стековой памяти мы имеем 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

введите описание изображения здесь

Автор: Nursnaaz Размещён: 07.02.2019 12:36

0 плюса

4534 Репутация автора

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

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

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

Например, это стандартная рекурсивная факториальная функция в 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 кадровых объектов.) Это вызывает ошибку переполнения стека . (Эй, отсюда и название этого сайта!)

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

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

Автор: Al Sweigart Размещён: 09.02.2019 12:13
Вопросы из категории :
32x32