хвостовая рекурсия против прямой рекурсии - PullRequest
Новая
       8

хвостовая рекурсия против прямой рекурсии

21 голосов
/ 15 июня 2010

Может ли кто-нибудь дать мне разницу между этими двумя видами рекурсий и примером (особенно в OCaml)?

Ответы [ 3 ]

28 голосов
/ 15 июня 2010

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

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

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

Например, факториальная функция часто пишется так на императивных языках: 

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

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

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

8 голосов
/ 15 июня 2010

Вот пример хвостовой рекурсивной факториальной функции: 

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 выполнять оптимизацию хвостового вызова, что приводит к переполнению стека.Обычно хвостовая рекурсивная функция будет использовать значение аккумулятора, чтобы обеспечить оптимизацию хвостового вызова.

0 голосов
/ 23 сентября 2017

Например, рекурсивная функция build_word, которая принимает char list и объединяет их в строку, т.е. ['f'; 'o'; 'o'] в строку "foo".Индукционный процесс можно представить следующим образом: 

build_word ['f'; 'o'; 'o']
"f" ^ (build_word ['o'; 'o'])
"f" ^ ("o" ^ (build_word ['o'])    // base case! return "o" and fold back
"f" ^ ("o" ^ ("o"))
"f" ^ ("oo")
"foo"

Это была нормальная рекурсия.Обратите внимание, что каждая пара скобок обозначает новый кадр стека или рекурсивный вызов.Решение этой проблемы (то есть "f", "fo" или "foo") не может быть получено до конца рекурсии (где встречается базовый случай).Только тогда последний кадр возвращает последний результат обратно к предыдущему, прежде чем «всплыть», и наоборот.

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

Версия хвостового вызова будет выглядеть примерно так: 

build_word ['f'; 'o'; 'o'] ""
build_word ['o'; 'o'], "f"
build_word ['o'] ("f" ^ "o")
build_word [] ("f" ^ "o" ^ "o")
"foo"

Здесь накопленный результат(часто хранится в переменной, известной как accumulator), передается вперед.С оптимизацией tail call не должен был бы создавать новый кадр стека, потому что он не должен поддерживать предыдущие.Решение решается «вперед», а не «назад».

Вот функции build_word в двух версиях:

non-tail 

let build_word chars = 
  match chars with
  | [] -> None
  | [c] -> Some Char.to_string c
  | hd :: tl -> build_word tl
;;

tail 

let build_word ?(acc = "") chars =
  match chars with
  | [] -> None
  | [c] -> Some Char.to_string c
  | hd::tl -> build_word ~acc:(acc ^ Char.to_string hd) tl
;;

Прямая рекурсия хорошо объяснена в принятом ответе @ sepp2k.

...