将递归函数转换为尾递归
我在ATS编码,并试图做一个函数,找到给定整数的平方根。 这里提供的代码能够正确满足我的需求,而不是尾递归。
implement intsqrt(n) =
if(n >= 1)
then let
val n4 = n / 4
val res = 2 * intsqrt(n4) + 1
in
if(res * res <= n) then res else 2*intsqrt(n4)
end
else n
我不确定其他人是否熟悉这种语言,但是这是我第一周了。 我知道常规和尾部递归之间的明显区别,我只是不明白这是如何改变的。
我甚至不需要确切的代码来做到这一点,我只是想知道它是如何可能的。 为了让我找到sqrt,我必须计算n4 = 1 / n,然后再乘以2。 但是,这样做会进入递归。 我想要做的是计算一个结果,然后传递给我的下一个递归调用。
这是否意味着我需要以某种方式倒退? 希望这一切都有道理,但我会尽力澄清,如果需要。
谢谢!
在模式匹配“伪代码”(Haskell,其中:
列表构建cons
和[]
空列表)中,你的函数是
isqrt n | n < 1 = n
| res*res <= n = res
| otherwise = 2 * isqrt(n `div` 4)
where
res = 2 * isqrt(n `div` 4) + 1
为了把它变成尾递归的,我们必须自己维护相关数据,比如说,在一个列表中。 首先简单地向n < 1
情况迭代,然后迭代返回,直到模拟堆栈耗尽并且可以产生最终结果。
转变很简单:
isqrt n = go n []
where
go n [] | n < 1 = n -- initial special case
go n (x:xs) | n < 1 = up n x xs -- bottom reached - start going back up
go n xs = go (n `div` 4) (n:xs) -- no - continue still down
up recres n (n1:ns) = -- still some way to go up
let res = 2*recres + 1
in if res*res <= n
then up res n1 ns -- "return" new recursive-result
else up (res-1) n1 ns -- up the chain of previous "invocations"
up recres n [] = -- the last leg
let res = 2*recres + 1
in if res*res <= n
then res -- the final result
else (res-1)
现在可以进一步简化代码。
做这种事情的系统方法是通过CPS转换。 以下实现的特别之处在于,在调用intsqrt_cps期间分配的每个内存字节在调用返回后都会释放。 这里没有GC(与上面的Haskell解决方案不同):
fun
intsqrt_cps
(
n: int, k: int -<lincloptr1> int
) : int =
if
(n >= 1)
then let
val n4 = n / 4
in
//
intsqrt_cps
( n4
, llam(res) =>
applin(k, if square(2*res+1) <= n then 2*res+1 else 2*res)
) (* intsqrt_cps *)
//
end // end of [then]
else applin(k, 0) // end of [else]
fun intsqrt(n:int): int = intsqrt_cps(n, llam(x) => x)
完整的代码可以在以下网址找到:
https://github.com/githwxi/ATS-Postiats/blob/master/doc/EXAMPLE/MISC/intsqrt_cps.dats
您可以使用valgrind来验证是否存在内存泄漏:
==28857== Memcheck, a memory error detector
==28857== Copyright (C) 2002-2015, and GNU GPL'd, by Julian Seward et al.
==28857== Using Valgrind-3.11.0 and LibVEX; rerun with -h for copyright info
==28857== Command: ./intsqrt_cps.exe
==28857==
intsqrt(1023) = 31
intsqrt(1024) = 32
==28857==
==28857== HEAP SUMMARY:
==28857== in use at exit: 0 bytes in 0 blocks
==28857== total heap usage: 14 allocs, 14 frees, 1,304 bytes allocated
==28857==
==28857== All heap blocks were freed -- no leaks are possible
==28857==
==28857== For counts of detected and suppressed errors, rerun with: -v
==28857== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)
链接地址: http://www.djcxy.com/p/80597.html