记忆化

-- The table memo keeps the results by argument
local function memoize(f)
  local memo = {}
  return function(x)
    local value = memo[x]
    if value == nil then
      value = f(x)
      memo[x] = value
    end
    return value
  end
end

-- calls shows how many times the body ran
local calls = 0
local function fibonacci(x)
  calls = calls + 1
  if x <= 1 then
    return x
  end
  return fibonacci(x - 1) + fibonacci(x - 2)
end

local mem_fibonacci = memoize(fibonacci)

local f20 = mem_fibonacci(20)
-- f20 = 6765
local calls_first = calls
-- calls_first = 21891

-- Cached: fibonacci is not called again
local f20_again = mem_fibonacci(20)
-- f20_again = 6765
local calls_second = calls
-- calls_second = 21891

-- Only the outer call is cached
local f21 = mem_fibonacci(21)
-- f21 = 10946
local calls_third = calls
-- calls_third = 57312

print("f20 = " .. f20)
print("calls_first = " .. calls_first)
print("f20_again = " .. f20_again)
print("calls_second = " .. calls_second)
print("f21 = " .. f21)
print("calls_third = " .. calls_third)