Turning recursive function into tail recursion

Question

I am coding in ATS and am trying to make a function that finds the square root of a given integer. Provided here is code that properly meets my requirments other than it not being tail-recursion.

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

I'm not sure if others know this language well or not but it is my first week with it. I know the clear difference between regular and tail recursion, I just don't understand how this can be changed.

I don't even need the exact code to do it, I am just wondering how it is possible. In order for me to find the sqrt, I must calculate n4 = 1 / n and then multiply it by two. However, doing this goes into the recursion. What I want to be able to do is calculate a result, then pass it through to my next recursive call.

Does this mean I need to work backwards in a way? Hopefully this all makes sense but I will try to clarify if needed.

Thanks!

Answer 1

In pattern-matching "pseudocode" (Haskell, where : is list-building cons and [] an empty list), your function is

isqrt n | n < 1 = n
        | res*res <= n = res
        | otherwise = 2 * isqrt(n `div` 4)
   where
        res = 2 * isqrt(n `div` 4) + 1

To turn it into a tail-recursive one we'll have to maintain the relevant data by ourselves, say, in a list. Simply iterate down towards the n < 1 case first, and then iterate back up until the simulated stack is exhausted and the final result can be produced.

The transformation is straightforward:

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)

The code can be simplified further now.