相互递归函数中的尾递归

Question

我有以下代码:

let rec f n =
    if n < 10 then "f" + g (n+1) else "f"
and g n =
    if n < 10 then "g" + f (n+1) else "g"

我想使这些相互递归的函数尾递归以进行优化.我尝试过以下方法:

let rec fT n = 
    let rec loop a = 
        if n < 10 then "f" + gT (a) else "f"
    loop (n + 1) 
and gT n =
    let rec loop a = 
        if n < 10 then "g" + fT (a) else "g"
    loop (n + 1) 

这是一个正确的尾递归版本吗？如果不是,将非常感谢正确方向的提示.

编辑(第二个解决方案):

let rec fA n = 
    let rec loop n a = 
        if n < 10 then loop (n + 1) ("f" + a) else a
    loop n "f"
and gA n =
    let rec loop n a = 
        if n < 10 then loop (n + 1) ("g" + a) else a
    loop n "g"

编辑(第三个解决方案):

let rec fA n a = 
    if n < 10 then gA (n + 1) (a + "f") else a
and gA n a =
    if n < 10 then fA (n + 1) (a + "g") else a

编辑(正确的解决方案):

let rec fA n a = 
    if n < 10 then gA (n + 1) (a + "f") else (a + "f")
and gA n a =
    if n < 10 then fA (n + 1) (a + "g") else (a + "g")

Answer 1

你的解决方案绝对不是尾递归的.

"Tail-recursion"就是这样的递归,其中每个递归调用都是函数执行的最后一个操作.这个概念很重要,因为它意味着运行时可以选择不在调用之间保持堆栈帧:因为递归调用是最后一件事,并且调用函数在此之后不需要执行任何其他操作,运行时可以跳过返回控制到调用函数,并让被调用函数返回到顶级调用者.这允许表达任意深度的递归算法,而不用担心耗尽堆栈空间.

但是,在您的实现中,函数fT.loop调用function gT,然后将"f"添加到gT返回的内容中."F"的这种预先考虑的情况发生后 gT已经返回,因此调用gT是不是说过去的事情fT.loop一样.因此,它不是尾递归的.

为了将"常规"递归转换为"尾部"类型,您必须"将逻辑内部转出",可以这么说.让我们看一下这个函数f:它调用g然后将"f"添加到g返回的内容中.这个"f"前缀是整个f计算中函数的整个"贡献" .现在,如果我们想要尾递归,这意味着我们不能在递归调用之后做出"贡献".这意味着贡献必须在此之前发生.但是如果我们在电话会议之前做出贡献并且之后没有做任何事情,那么我们如何避免失去这一贡献呢？唯一的方法是将贡献作为参数传递给递归调用.

这是尾递归计算背后的一般思想:我们不是等待嵌套调用完成然后向输出添加内容,而是先进行添加,然后将已经"添加到目前为止"的内容传递给递归调用.

回到你的具体例子:由于贡献f是"f"字符,它需要将这个字符添加到"到目前为止"计算的内容并将其传递给递归调用,然后执行相同的操作,等等上."到目前为止"的论证应该具有"计算你要计算的任何东西,然后将我的'到目前为止'添加到那个"的语义.

因为你只是要求"暗示",这显然是家庭作业(如果我错了就原谅我),我不会发布实际的代码.如果你愿意我做,请告诉我.