从简单的任务开始,例如在列表中将项从'a映射到'b。我们想编写一个函数,其签名为
val map: ('a -> 'b) -> 'a list -> 'b list
在哪里
map (fun x -> x * 2) [1;2;3;4;5] == [2;4;6;8;10]
从非尾递归版本开始:
let rec map f = function
| [] -> []
| x::xs -> f x::map f xs
这并不是尾递归,因为在进行递归调用之后函数仍需继续工作。::
是 List.Cons(f x, map f xs)
的语法糖。
如果我将最后一行重写为 | x::xs -> let temp = map f xs; f x::temp
,函数的非递归性可能会更为明显-- 显然它在递归调用之后还要做一些工作。
使用一个累加器变量使其成为尾递归:
let map f l =
let rec loop acc = function
| [] -> List.rev acc
| x::xs -> loop (f x::acc) xs
loop [] l
这里我们在一个变量acc
中构建一个新列表。由于列表是反向构建的,所以在将输出列表返回给用户之前,我们需要将其反转。
如果你想要尝试一些有趣的编程技巧,可以使用续传来更简洁地编写代码:
let map f l =
let rec loop cont = function
| [] -> cont []
| x::xs -> loop ( fun acc -> cont (f x::acc) ) xs
loop id l
由于调用loop
和cont
是最后一个没有额外工作的函数调用,它们是尾递归的。
这是因为续延cont
被一个新的续延所捕获,而这个新的续延又被另一个续延所捕获,从而形成了一种类似树状数据结构的东西,如下所示:
(fun acc -> (f 1)::acc)
((fun acc -> (f 2)::acc)
((fun acc -> (f 3)::acc)
((fun acc -> (f 4)::acc)
((fun acc -> (f 5)::acc)
(id [])))))
它按顺序构建列表,无需反转。
值得一提的是,以非尾递归的方式编写函数更易于阅读和使用。
如果您有一个要遍历的大型列表,请使用累加器变量。
如果您找不到方便使用累加器的方法,并且没有其他可用选项,请使用continuations。我个人认为,复杂的continuations使用难以阅读。
id
是F#自带的内置函数之一,其定义为let id x = x
。 - Julietloop (f x::acc) xs
调用递归函数,然而递归函数只接收一个参数,所以这不会编译吧?也许我对 function 关键字有些不理解,实际上我还从未使用过它(可以使用 fun
关键字代替吗?) - knoctefunction
关键字会向函数添加一个参数。请参阅 https://markhneedham.com/blog/2010/02/07/f-function-keyword/。 - Gabriel相较于其他示例,这是一种更简短的解释尝试:
let rec foo n =
match n with
| 0 -> 0
| _ -> 2 + foo (n-1)
let rec bar acc n =
match n with
| 0 -> acc
| _ -> bar (acc+2) (n-1)
在这里,foo
不是尾递归的,因为为了计算 2+foo(n-1)
并返回它,foo
必须要递归调用自身。
然而,bar
是尾递归的,因为 bar
不需要使用递归调用的返回值就可以返回一个值。它只需让被递归调用的 bar
立即返回其值(而不是一直返回到调用堆栈上)即可。编译器会看到这个优化,把递归改写成循环。
将 bar
中的最后一行改为类似于 | _ -> 2 + (bar (acc+2) (n-1))
的语句会破坏函数的尾递归性,因为 2+
需要在递归调用结束后执行。
这里有一个更明显的例子,将其与您通常为阶乘所做的比较。
let factorial n =
let rec fact n acc =
match n with
| 0 -> acc
| _ -> fact (n-1) (acc*n)
fact n 1
这个有点复杂,但主要思想是使用累加器来保持一个持续更新的总数,而不是修改返回值。
另外,这种包装风格通常是一个好主意,这样你的调用者就不需要担心如何初始化累加器(注意,该事实仅局限于函数内部)。
let rec fib = function
| n when n < 2 -> 1
| n -> fib(n-1) + fib(n-2);;
尾递归版本
let fib n =
let rec tfib n1 n2 = function
| 0 -> n1
| n -> tfib n2 (n2 + n1) (n - 1)
tfib 0 1 n;;
tfib 0 1 n
替换为tfib 0I 1I n
以利用F#中的Numerics.BigInteger结构。