问为什么这个函数不是尾递归函数？
EN

Stack Overflow用户

提问于 2013-11-19 10:56:08

回答 4查看 227关注 0票数 2

我想读取出现在文件中的数据(数据由另一个进程写入)。比如“持续阅读”。

简单的代码将文件读到最后并完成，没有任何问题：

let readStream (r: StreamReader) =
  seq {
    while not r.EndOfStream do
      yield r.ReadLine() }

现在，我向它添加了以下逻辑:如果它到达流的末尾，它将等待一秒钟，然后重试。如果数据没有出现，它会休眠2秒，然后在5次尝试中休眠5秒：

let readStream (r: StreamReader) =
    let rec loop waitTimeout waits =
        seq {
            match waitTimeout with
            | None -> 
                if not r.EndOfStream then 
                    yield r.ReadLine()
                    yield! loop None 0
                else yield! loop (Some 1000) waits
            | Some timeout when waits < 5 -> 
                let waits = waits + 1
                printfn "Sleeping for %d ms (attempt %d)..." timeout waits
                Thread.Sleep (timeout * waits)
                yield! loop None waits
            | _ -> ()
        }
    loop None 0

不幸的是，它被证明是非尾递归的，应用程序很快就崩溃了，并出现了StackOverflow异常。

有人能帮上忙吗？

.net

lazy-evaluation

tail-recursion

TDSQL-CMySQL免费体验

云原生数据库TDSQL-C MySQL 2核4G 免费体验15天

回答 4

Stack Overflow用户

发布于 2013-11-19 12:14:37

在进入更多细节之前，您是否也在debug中启用了生成尾部调用？(默认情况下，F#不在调试代码中执行尾部调用。)

编辑:好吧，你的返回值最终是一个seq {...}，而不是loop x y的值。因此，您实际上是在构建一个嵌套序列，而不是使用尾递归。

尝试以这样一种方式重写代码，即不使用嵌套序列，而是在序列中使用尾递归。

票数 1

Stack Overflow用户

发布于 2013-11-19 14:52:34

正如Daniel指出的，根据定义，具有序列表达式的主体的函数不是尾递归的，因为任何递归调用都是延迟的。这也保证了调用readStream不会导致堆栈溢出-它只会返回一个不透明的seq<string>值。因此，堆栈溢出的原因至少部分取决于调用代码。

票数 1

Stack Overflow用户

发布于 2013-11-20 14:29:22

嗯，你写的代码对我来说也很好(在F# 3.0上)。正如kvb所指出的，你的消费者代码有问题吗？

type Reader(k) =
    let mutable n = 0
    member __.EndOfStream = n >= k
    member __.ReadLine() = n <- n + 1; "OK"

let readStream (r: Reader) =
    let rec loop waitTimeout waits =
        seq {
            match waitTimeout with
            | None -> 
                if not r.EndOfStream then 
                    yield r.ReadLine()
                    yield! loop None 0
                else yield! loop (Some 1000) waits
            | Some timeout when waits < 5 -> 
                let waits = waits + 1
                printfn "Sleeping for %d ms (attempt %d)..." timeout waits
                System.Threading.Thread.Sleep(timeout * waits)
                yield! loop None waits
            | _ -> ()
        }
    loop None 0

let test () =
    readStream (Reader 2000000)
    |> Seq.length