将递归函数变成尾递归

Question

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

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

谢谢！

Answer 1

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

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