我需要在OCaml中编写一个函数,在两个不同的递归中添加两个列表的元素:simple和tail。我做了一个简单的:
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,因为在第一个列表中的这个位置上并没有元素。
所以,我的问题是:
如何使用尾部递归?
使这个尾部递归的方法是向后构建结果,并在递归中传递它,最后反转它。
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也可以附加空列表,因此不需要匹配([],[](。
尾递归包含递归函数,该函数只执行对自身的调用,而不执行任何其他操作。
下面的阶乘不是尾递归的,因为最后一条语句不执行对事实的简单调用,而是需要一个multiplcation:
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
对于列表添加,如果两个列表的长度至少相同,则可以以相同的方式进行添加。