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

Question

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

Answer 1

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

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

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

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

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

Answer 2

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

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

Answer 3

Например, рекурсивная функция 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") не может быть получено до конца рекурсии (где встречается базовый случай). Только тогда последний кадр возвращает последний результат к предыдущему, прежде чем "всплыть", и наоборот.

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

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

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 функции в двух версиях:

без хвоста

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

хвост

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.