14

Lua は、末尾呼び出しを適切に実装しているため、呼び出しごとにスタックを維持する必要がないため、無限再帰が可能であると主張しています。合計関数を作成しようとしました。1 つは末尾呼び出しではなく、もう 1 つは末尾呼び出しです。

無テイルコールバージョン

function sum(n)
    if n > 0 then
        return n + sum(n-1)
    end
end

print(sum(1000000))

期待通りのスタックオーバーフロー。

テールコールバージョン

function sum2(accu, n)
    if n > 0 then
        accu.value = accu.value + n
        sum2(accu, n-1)
    end
end
local accu = {value = 0}
sum2(accu, 1000000)
print(accu.value)

この場合はテールコールであるため、スタックオーバーフローは発生しないと思いますが、スタックオーバーフローが原因で失敗しました。

/bin/lua/5.1.4/bin/lua: tailcall.lua:13: stack overflow
stack traceback:
        tailcall.lua:13: in function 'sum2'
        tailcall.lua:13: in function 'sum2'
        tailcall.lua:13: in function 'sum2'
        tailcall.lua:13: in function 'sum2'
        tailcall.lua:13: in function 'sum2'
        tailcall.lua:13: in function 'sum2'
        tailcall.lua:13: in function 'sum2'
        tailcall.lua:13: in function 'sum2'
        tailcall.lua:13: in function 'sum2'
        tailcall.lua:13: in function 'sum2'
        ...
        tailcall.lua:13: in function 'sum2'
        tailcall.lua:13: in function 'sum2'
        tailcall.lua:13: in function 'sum2'
        tailcall.lua:13: in function 'sum2'
        tailcall.lua:13: in function 'sum2'
        tailcall.lua:13: in function 'sum2'
        tailcall.lua:13: in function 'sum2'
        tailcall.lua:13: in function 'sum2'
        tailcall.lua:17: in main chunk
        [C]: ?

lua は本当に末尾呼び出しの最適化をサポートしていますか、それとも私の関数は実際には末尾呼び出しではありませんか?

redhat 5でlua 5.1.4を使用しています

4

1 に答える 1

22

Lua のテール コールは次の形式にする必要があります。

return fct(args)

したがって、テール コールのバージョンは次のように書き換える必要があります。

function sum2(accu, n)
  if n > 0 then
    accu.value = accu.value + n
    return sum2(accu, n-1) --< note the return here
  end
end
于 2012-11-09T07:53:39.280 に答える