为什么这不是尾递归
Why is this not tail recursive
我有一对(co?)递归函数,可以处理元组列表,并根据一些开始和结束条件将它们折叠成批次。
我不经常做 f# 所以我可能是愚蠢的。
我已经修改了一个简单的非尾递归版本,通过显式引入构成当前折叠状态的 "tot" 参数,我认为是尾递归,但我得到了可怕的堆栈大输入溢出....(在调试器和(调试).exe 中)
可能有一个更好的方法作为显式折叠...但这几乎不是重点,重点是为什么它看起来不是尾递归?
let rec ignoreUntil2 (xs : List<(string * string)>) tot = //: List<(string * string)> -> List<List<(string * string)>> -> List<List<(string * string)>> =
match xs with
| [] -> tot
| ((s1,s2)::tail) ->
if s2.StartsWith("Start importing record: Product") then
takeUntil2 [] ((s1,s2)::tail) tot
else
ignoreUntil2 tail tot
and takeUntil2 acc xs tot = // : List<(string * string)> -> List<(string * string)> -> List<List<(string * string)>> -> List<List<(string * string)>> =
match xs with
| [] -> acc :: tot
| ((s1,s2)::tail) ->
let newAcc = ((s1,s2)::acc)
if s2.StartsWith("Finished importing record: Product") then
ignoreUntil2 tail (newAcc :: tot)
else
takeUntil2 newAcc tail tot
您的代码是尾递归。
(in both debugger and (debug) .exe)
默认情况下,F# 编译器不会在调试模式下消除尾调用。您需要显式启用 --tailcalls
选项或在发布模式下编译。
我有一对(co?)递归函数,可以处理元组列表,并根据一些开始和结束条件将它们折叠成批次。
我不经常做 f# 所以我可能是愚蠢的。
我已经修改了一个简单的非尾递归版本,通过显式引入构成当前折叠状态的 "tot" 参数,我认为是尾递归,但我得到了可怕的堆栈大输入溢出....(在调试器和(调试).exe 中)
可能有一个更好的方法作为显式折叠...但这几乎不是重点,重点是为什么它看起来不是尾递归?
let rec ignoreUntil2 (xs : List<(string * string)>) tot = //: List<(string * string)> -> List<List<(string * string)>> -> List<List<(string * string)>> =
match xs with
| [] -> tot
| ((s1,s2)::tail) ->
if s2.StartsWith("Start importing record: Product") then
takeUntil2 [] ((s1,s2)::tail) tot
else
ignoreUntil2 tail tot
and takeUntil2 acc xs tot = // : List<(string * string)> -> List<(string * string)> -> List<List<(string * string)>> -> List<List<(string * string)>> =
match xs with
| [] -> acc :: tot
| ((s1,s2)::tail) ->
let newAcc = ((s1,s2)::acc)
if s2.StartsWith("Finished importing record: Product") then
ignoreUntil2 tail (newAcc :: tot)
else
takeUntil2 newAcc tail tot
您的代码是尾递归。
(in both debugger and (debug) .exe)
默认情况下,F# 编译器不会在调试模式下消除尾调用。您需要显式启用 --tailcalls
选项或在发布模式下编译。