1

我被要求将此 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;;

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

4

1 回答 1

0

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

las，您的版本不是尾递归的，因为您的运算符优先级错误。累加器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

您可以更进一步并使用连续传递样式 (CPS)，将累加器替换为组合函数，每个函数的参数都加 1。这也将编译成一个循环并保留堆栈空间，代价是存储函数链所需的内存。

此外，您可以重新考虑参数的顺序：首先使用累加器（或延续），最后使用列表允许使用function关键字。

let rec lenk k = function
| [] -> k 0 
| x::xr -> lenk (k << (+) 1) xr

[0..1000000] |> lenk id      // val it : int = 1000001
于 2020-11-04T21:20:02.433 回答