Luaの再帰
再帰アルゴリズムを実装し、Luaの末尾呼び出し最適化を理解します。
「Luaの再帰」はCoddyKit上の無料Lua Academyレッスンです。 これはレッスン4/4です。 下記で完全なレッスンを無料で読むことができます。その後、ブラウザ内の組み込みコードエディタと24時間対応のAIチューターでハンズオン演習できます。 これはLua Academy学習パスの一部であり、ウェブとCoddyKitアプリ全体で進捗が同期されます。 Lua Academyコースには全4レッスンが含まれています。
再帰とは
再帰とは、関数が同じ問題のより小さな問題を解くために、自分自身を呼び出すことです。すべての再帰関数には、停止する基本ケースと、問題を小さくする再帰ケースが必要です。基本ケースがないと、再帰によってスタックオーバーフローが発生します。
local function countdown(n)
if n <= 0 then
print("Blast off!")
return
end
print(n)
countdown(n - 1)
end
countdown(5)
-- 5, 4, 3, 2, 1, Blast off!階乗
階乗は再帰の典型的な例です：n! = n × (n-1)!。基本ケースは 0! = 1 です。各呼び出しで n が1ずつ減少し、基本ケースに到達します。結果は呼び出しスタックを「巻き戻り」ながら戻り、その過程で掛け合わされます。
local function factorial(n)
if n <= 1 then return 1 end
return n * factorial(n - 1)
end
print(factorial(1)) -- 1
print(factorial(5)) -- 120
print(factorial(10)) -- 3628800フィボナッチ数列
フィボナッチ数列も典型的な例です：fib(n) = fib(n-1) + fib(n-2)。素朴な再帰は指数時間で、同じ値を何度も再計算します。これを解決するメモ化については後で説明しますが、まずは基本形を見ていきます。
local function fib(n)
if n <= 1 then return n end
return fib(n - 1) + fib(n - 2)
end
for i = 0, 10 do
io.write(fib(i) .. " ")
end
print()
-- 0 1 1 2 3 5 8 13 21 34 55メモ化再帰
メモ化では、計算済みの結果をテーブルにキャッシュします。呼び出しごとに、まずキャッシュを確認します。値があればすぐに返し、なければ計算して保存します。これにより、指数時間のフィボナッチ計算を線形時間に変えられます。
local memo = {}
local function fib(n)
if memo[n] then return memo[n] end
if n <= 1 then return n end
local result = fib(n-1) + fib(n-2)
memo[n] = result
return result
end
print(fib(40)) -- 102334155 (fast!)末尾呼び出し最適化
Luaは末尾呼び出し最適化（TCO）を行います。関数の最後の処理が別の関数の呼び出しである場合、Luaは現在のスタックフレームを再利用します。これにより、末尾再帰関数はO(1)のスタック領域で動作します。すべての再帰が末尾再帰になるわけではありません。呼び出しが関数内の最後の処理である必要があります。
-- Tail-recursive factorial using accumulator
local function factTail(n, acc)
acc = acc or 1
if n <= 1 then return acc end
return factTail(n - 1, n * acc) -- tail call
end
print(factTail(10)) -- 3628800
-- Can handle very large n without stack overflow木の走査
再帰は木構造の走査を自然に表現できます。木は value、left、right フィールドを持つテーブルです。先行順、中間順、後行順の走査は、再帰呼び出しに対して値を処理するタイミングだけが異なります。
local function inorder(node)
if node == nil then return end
inorder(node.left)
io.write(node.value .. " ")
inorder(node.right)
end
local tree = {
value=4,
left={value=2, left={value=1}, right={value=3}},
right={value=6, left={value=5}, right={value=7}}
}
inorder(tree) -- 1 2 3 4 5 6 7相互再帰
2つの関数が互いを呼び出すことを相互再帰といいます。Luaでは前方宣言が必要です。まずローカル変数を宣言し、その後で関数を代入します。これにより、各関数は、すでにスコープ内にあるもう一方の関数の変数を参照できます。
local isEven, isOdd
isEven = function(n)
if n == 0 then return true end
return isOdd(n - 1)
end
isOdd = function(n)
if n == 0 then return false end
return isEven(n - 1)
end
print(isEven(10)) -- true
print(isOdd(7)) -- true再帰的な深いコピー
再帰は、入れ子になった構造の処理に適しています。テーブルの深いコピーとは、その内容をコピーし、入れ子になったテーブルも再帰的にコピーすることです。これにより、コピーを変更しても元のテーブルには影響しません。
local function deepCopy(orig)
local copy
if type(orig) == "table" then
copy = {}
for k, v in pairs(orig) do
copy[deepCopy(k)] = deepCopy(v)
end
setmetatable(copy, getmetatable(orig))
else
copy = orig
end
return copy
end
local a = {1, {2, 3}}
local b = deepCopy(a)
b[2][1] = 99
print(a[2][1]) -- 2 (unchanged)塗りつぶしアルゴリズム
塗りつぶし（ペイントプログラムやゲームマップで使われます）は、自然に再帰で表現できます。あるセルから開始して印を付け、未訪問の隣接セルを再帰的に塗りつぶします。境界または訪問済みのセルに達すると再帰が終了します。
local grid = {
{0,0,0,1,0},
{0,1,0,1,0},
{0,1,1,1,0},
{0,0,0,0,0},
}
local function fill(g, r, c)
if r<1 or r>#g or c<1 or c>#g[r] then return end
if g[r][c] ~= 0 then return end
g[r][c] = 2 -- mark visited
fill(g,r-1,c); fill(g,r+1,c)
fill(g,r,c-1); fill(g,r,c+1)
end
fill(grid, 1, 1)
print(grid[1][1], grid[2][1]) -- 2 2スタックの深さへの注意
Luaのデフォルトの呼び出しスタックには制限があります（末尾呼び出しでない場合、通常は約200レベル）。深い非末尾再帰を行うと、「stack overflow」エラーが発生します。解決策として、末尾再帰に変換する、明示的なスタック（テーブル）を使う、大規模な反復処理にはコルーチンを使う方法があります。
-- Simulate deep recursion danger
local function depth(n)
if n == 0 then return "done" end
return depth(n - 1) -- tail call, safe
end
print(depth(100000)) -- done (tail call, no overflow)
-- Non-tail: limited depth
local function countDown(n)
if n == 0 then return 0 end
return 1 + countDown(n - 1) -- NOT a tail call
end
-- countDown(10000) would stack overflow確認問題
次のうち、Luaで正しい末尾呼び出しはどれですか？
復習：再帰
まとめ：
- すべての再帰関数には基本ケースと再帰ケースが必要です
- 末尾呼び出し（最後の処理が呼び出し）はLuaによって最適化され、スタック使用量はO(1)になります
- メモ化により、指数時間の再帰を線形時間に変えられます
- 相互再帰には前方宣言が必要です
- 木やグラフの深い再帰は自然な方法ですが、非末尾呼び出しではスタックの深さに注意してください
よくある質問
「Luaの再帰」レッスンは無料ですか？
はい。「Luaの再帰」の完全なテキストはこのウェブで無料で読めます。インタラクティブに演習し（組み込みコードエディタと24時間対応のAIチューター）、Lua Academyコースの残りをアンロックするには、CoddyKit PROにアップグレードしてください。 Lua Academyコースには全4レッスンが含まれています。
「Luaの再帰」で何を学びますか？
再帰アルゴリズムを実装し、Luaの末尾呼び出し最適化を理解します。 ブラウザで直接実行するハンズオンコードでLua Academyを演習し、24時間対応のAIチューターがレッスンを進める中での質問に答えます。
Lua Academyを始めるのに経験は必要ですか？
事前経験は必要ありません。CoddyKitのLua Academyは初級者から上級者向けに構成されているため、ここから始めるか最初から始めて、自分のペースで進むことができます。 これはレッスン4/4です。
「Luaの再帰」レッスンにはどのくらい時間がかかりますか？
ほとんどのCoddyKitレッスンは約5～10分かかります。各レッスンはコンパクトでインタラクティブなので、着実に進歩し、ウェブとアプリ全体で正確に前回の場所から再開できます。
このLua Academyレッスンでコードを書いて実行できますか？
はい。すべてのLua Academyレッスンに組み込みコードエディタが含まれているため、ブラウザでリアルコードを書いて実行し、即座のAIフィードバックを取得できます。ローカル設定は不要です。