การเรียกซ้ำใน Lua

การเรียกซ้ำคืออะไร

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!

แฟกทอเรียล

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

ฟีโบนัชชี

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!)

การเพิ่มประสิทธิภาพการเรียกแบบหาง

-- 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

การท่องผ่านต้นไม้

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

การเรียกซ้ำร่วมกัน

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

การตระหนักถึงความลึกของสแตก

-- 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

ตรวจสอบอย่างรวดเร็ว

ทบทวน: การเรียกซ้ำ