gpt4 book ai didi

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

转载 作者:行者123 更新时间:2023-12-01 10:22:02 25 4
gpt4 key购买 nike

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

显然,最后评估的 Action 不是递归调用,因此给定的实现确实会抛出足够大的l

那么有什么方法(如果有的话)重写递归,使 1) 保持递归,2) 成为尾部优化?我假设 phi n l result 会起作用,但是不能相应地重新定义...是否有可靠的方法/技术来解决此类问题?

最佳答案

所以你有这个计算树:

               +                 l              ╱ ╲             1   ÷                ╱ ╲               1   +             l-1                  ╱ ╲                 1   ÷                    ╱ ╲                   1  ...                        ╲                         +       1                        ╱ ╲                       1   ÷                          ╱ ╲                         1   1   0

Since this has a linear shape, you can indeed make it tail-recursive. For this you need to start at the bottom and keep the already-calculated right result in an accumulator variable.

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错误。

关于haskell - 这个特定的递归可以用尾部优化的方式重写吗?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/50201660/

25 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com