Как написать функцию, которая добавляет элементы списка, используя хвостовую рекурсию? - PullRequest
Новая
       6

Как написать функцию, которая добавляет элементы списка, используя хвостовую рекурсию?

0 голосов
/ 05 ноября 2018

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

let rec add1 a b = 
match (a, b) with
      ([], []) -> []
    | (head1::tail1, []) -> head1 :: add1 tail1 []
    | ([], head2::tail2) -> head2 :: add1 [] tail2
    | (head1::tail1, head2::tail2) -> head1 + head2 :: add1 tail1 tail2
;;

Работает так: 

add1 [1;2;3] [4;5;6;7];;

Это возвращение: 

int list = [5; 7; 9; 7]

[1+4; 2+5; 3+6; 0+7]: 0 добавлено к 7, потому что в первом списке нет элементов с такой позицией.

Итак, мой вопрос:

Как я могу сделать это с хвостовой рекурсией?

Ответы [ 2 ]

0 голосов
/ 05 ноября 2018

Способ сделать этот хвост рекурсивным - построить результат задом наперед, передать его в рекурсии и обратить его в конце. 

let add1 a b =
  let rec loop acc = function
    | (xs, [])
    | ([], xs) -> List.rev_append acc xs
    | (x::xs, y::ys) -> loop ((x + y)::acc) (xs, ys)
  in
  loop [] (a, b)

Примечание. Если один список длиннее другого, вам не нужно добавлять 0 к каждому элементу. Хвост - это уже результат. Поэтому я использую List.rev_append, чтобы сторнировать накопленные значения и добавить оставшийся хвост за один раз.

Примечание 2: List.rev_append также может добавлять пустой список, поэтому совпадение для ([], []) не требуется.

0 голосов
/ 05 ноября 2018

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

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

    let rec fact n = 
        if n = 0 then 1
        else n*(fact (n-1))

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

    let rec fact n r =
        if n = 0 then r
        else fact (n-1) (r*n)

И использование: 

    fact 5 1

Для добавления списков вы можете действовать одинаково, если два списка имеют одинаковую длину по крайней мере.

...