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

Ответ 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

Теперь это и рекурсия вперед, и хвостовая рекурсия, потому что рекурсивный вызов: a) хвостовой вызов и b) вызывает себя с большим значением (i+1).

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

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

В теории каждый вызов создает новый стек стека (или область, если хотите), чтобы удерживать "место" для фрагментированного решения, которое нужно вернуть и собрать в начале. Это может привести к fooobar.com/info/4776/... (эта ссылка является рекурсивной btw).

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

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

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

Вот функции 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.