Включение рекурсивной функции в хвостовую рекурсию

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)