хвостовая рекурсия по сравнению с вперед рекурсией
Кто-то может дать мне различие между этими двумя рекурсиями видов и примером (конкретно в OCaml)?
2 ответа
Хвостовая рекурсивная функция - это функция, в которой единственный рекурсивный вызов является последним в функции. Не хвостовая рекурсивная функция - это функция, в которой это не так.
Обратная рекурсия - это рекурсия, в которой в каждом рекурсивном вызове значение параметра меньше, чем на предыдущем шаге. Прямая рекурсия - это рекурсия, которая увеличивается с каждым шагом.
Это две ортогональные концепции, то есть прямая рекурсия может быть хвостовой рекурсией, а может и не быть, и то же самое применимо к обратной рекурсии.
Например, на императивных языках функция факториала часто записывается следующим образом:
fac = 1
for i from 1 to n:
fac := fac * i
Обычная рекурсивная версия факториала ведет счет в обратном порядке (то есть вызывает себя с параметром n-1 в качестве параметра), однако если если бы вы прямо перевели указанное выше императивное решение, вы бы получили рекурсивную версию, которая считается в возрастающем порядке. Это будет выглядеть примерно так:
let fac n =
let rec loop i =
if i >= n
then i
else i * loop (i+1)
in
loop 1
Это прямая рекурсия, и, как вы можете видеть, она немного более громоздка, чем обратная рекурсивная версия, поскольку требует вспомогательной функции. Теперь это не хвостовая рекурсия, поскольку последний вызов в цикла - это умножение, а не рекурсия. Итак, чтобы сделать его хвостовой рекурсией, вы должны сделать что-то вроде этого:
let fac n =
let rec loop acc i =
if i >= n
then acc
else loop (i*acc) (i+1)
in
loop 1 1
Теперь это и прямая рекурсия, и хвостовая рекурсия, потому что рекурсивный вызов - это а) хвостовой вызов и б) вызывает сам себя с большим значением ( i + 1 ).
Вот пример хвостовой рекурсивной факториальной функции:
let fac n =
let rec f n a =
match n with
0 -> a
| _ -> f (n-1) (n*a)
in
f n 1
Вот ее не хвостовой рекурсивный аналог:
let rec non_tail_fac n =
match n with
0 -> 1
| _ -> (non_tail_fac n-1) * n
Хвост рекурсивная функция использует аккумулятор a для хранения значения результата предыдущего вызова. Это позволяет OCaml выполнять оптимизацию хвостового вызова, в результате чего стек не переполняется. Обычно хвостовая рекурсивная функция будет использовать значение аккумулятора, чтобы обеспечить оптимизацию хвостового вызова.