长度函数的尾部递归版本是否在运行时节省堆栈空间

Question

我被要求将F#length函数更改为尾部递归函数。

let rec len xs = 
match xs with 
| [] -> 0 
| x::xr -> 1 + len xr;;

虽然这不是一个困难的练习，但我想知道是否要更改为尾部递归版本，比如下面的

let rec leni xs r = 
match xs with 
| [] -> r 
| x::xr -> leni xr r+1;;

与非尾部递归相比，运行时确实节省了堆栈空间？

Answer 1

尾递归函数被编译成一个循环，它们不使用任何依赖于迭代次数的额外堆栈。

遗憾的是，您的版本不是尾部递归的，因为您的运算符的优先级是错误的。累加器r被解释为属于递归调用，它被原封不动地传递给递归调用。因此，函数需要返回以使其返回值递增。

让我们看看：

let rec len xs = 
match xs with 
| [] -> 0 
| x::xr -> 1 + len xr;;
let rec leni xs r = 
match xs with 
| [] -> r 
| x::xr -> leni xr r+1;;
[0..10000] |> len     // val it : int = 10001
[0..100000] |> len    // val it : int = 100001
[0..1000000] |> len   // Process is terminated due to StackOverflowException.
([0..1000000], 0) ||> leni   // Process is terminated due to StackOverflowException.

修复方法只是将新的累加器值用括号括起来，再加1

let rec leni' xs r = 
match xs with 
| [] -> r 
| x::xr -> leni' xr (r+1)
([0..1000000], 0) ||> leni'   // val it : int = 1000001

您可以更进一步，使用Continuation Passing Style(CPS(，用组合函数替换累加器，每个函数的参数加1。这也将编译成一个循环并保留堆栈空间，以牺牲存储函数链所需的内存为代价。

此外，您还可以重新考虑参数的顺序：首先使用累加器(或连续(，最后使用列表，这样就可以使用function关键字。

let rec lenk k = function
| [] -> k 0 
| x::xr -> lenk (k << (+) 1) xr
[0..1000000] |> lenk id      // val it : int = 1000001