Превращение рекурсивной функции в хвостовую рекурсию

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, а затем умножить его на два. Тем не менее, выполнение этого входит в рекурсию. Я хочу вычислить результат и передать его следующему рекурсивному вызову.

Значит ли это, что мне нужно работать в обратном направлении? Надеюсь, все это имеет смысл, но я постараюсь уточнить, если это необходимо.

Спасибо!

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)

Код теперь может быть упрощен.

Answer 2

Систематический способ сделать это - через 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)