将递归函数转换为尾递归

我在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。但是，这样做会进入递归。我想要做的是计算一个结果，然后传递给我的下一个递归调用。

这是否意味着我需要以某种方式向后工作？希望这一切都有道理，但我会尽力澄清，如果需要。

谢谢！

来源

2016-01-25 rmw

你确定你的算法是正确的吗？我将它翻译成Scheme，它适用于4和16，但不适用于9和25，除非我在翻译过程中发生错误。 – uselpa

@uselpa据我所知是的。这是一项任务，提示是“对于每个n> = 1，让n4 = n/4。然后sqrt（n）= 2 * sqrt（n4）或 sqrt（n）= 2 * sqrt（n4）+ 1.”即使它可能不适用于每个数字，你是否看到任何可行的方法将其变为尾递归？ – rmw

@uselpa我得到了3.据我所知，它的工作原理应该如何。这更多的是关于如何构建我的代码。 – rmw

在模式匹配“伪”（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)

的代码可以进一步现在被简化。

来源

2016-01-27 21:47:39

做这种事情的系统方法是通过CPS转换。以下实现的特别之处在于调用intsqrt_cps期间分配的每个内存字节在调用返回后都会释放。这里没有GC（不同于上述的Haskell溶液）：

https://github.com/githwxi/ATS-Postiats/blob/master/doc/EXAMPLE/MISC/intsqrt_cps.dats

可以使用的valgrind来验证不存在存储器泄漏：

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)

代码的整体，可以发现：

==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)

来源

2016-10-17 13:40:02

将递归函数转换为尾递归

回答

相关问题