代码之家 › 专栏 › 技术社区 › Zazaeil

这个特定的递归可以用尾部优化的方式重写吗?

tail-recursion functional-programming recursion haskell

Zazaeil · 技术社区 · 6 年前

phi n 0 = 1
phi n l = 1 + 1 / phi n (l - 1)

显然,上次评估的操作不是递归调用,因此给定的实现确实抛出了足够大的 l 。

那么,重写递归的方法(如果有的话)是什么,以便1)它保持递归,2)变得尾部优化?我想 phi n l result 将起作用,但无法相应地重新定义。。。是否有可靠的方法/技术来解决此类问题?

1 回复 | 直到 6 年前

leftaroundabout 6 年前

所以你有这个计算树:

               +                 l
              â± â²
             1   Ã·
                â± â²
               1   +             l-1
                  â± â²
                 1   Ã·
                    â± â²
                   1  ...
                        â²
                         +       1
                        â± â²
                       1   Ã·
                          â± â²
                         1   1   0

因为这是一个线性形状,所以确实可以使其尾部递归。为此,您需要从底部开始,并将已计算的正确结果保留在累加器变量中。

phi _ l = go 0 1  -- n isn't actually used
 where go l' acc
        | l' < l     = go (l'+1) $! 1 + 1/acc
        | otherwise  = acc

未测试,此处可能存在off-by-1错误。

推荐文章

jkfe · 为什么println会在这段递归代码中执行?

2 年前

Brian Patterson · Javascript自定义数组。原型方法日志“未定义”

2 年前

Jimmy · 这种算法怎么能按顺序遍历树“爬上”树呢?

2 年前

iRon · 匿名递归函数

2 年前

ProgrammingNoob321312 · 为什么这个Java代码会输出“3210123”?

2 年前

AvirukBasak · gcc中无return语句的尾部递归

2 年前

Dharmik Patel · 使用python递归完全可以整除

2 年前

W.tan · 一维最短距离递归算法

2 年前

ncarrawa · 将1添加到i(递归)时出现类型错误

2 年前

Eren · Python递归何时返回[duplicate]

2 年前