0Pricing
Lua Academy · 课时

Lua 中的递归

实现递归算法，并理解 Lua 的尾调用优化。

Lua 中的递归 是 CoddyKit 上的免费 Lua Academy 课时。 这是第 4 节课，共 4 节。 你可以在下方免费阅读本课时的完整内容 — 然后在浏览器中使用内置代码编辑器和全天候 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

相互递归

两个函数可以相互调用，这称为相互递归。在 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 层）。深度非尾递归会导致“栈溢出”错误。解决方案包括：改写为尾递归、使用显式栈（表），或使用协程处理大型迭代任务。

-- 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 中的递归」的完整文本可在网页上免费阅读。要进行交互式练习（内置代码编辑器和全天候 AI 导师）并解锁 Lua Academy 课程的其余内容，请升级到 CoddyKit PRO。 Lua Academy 课程共包含 4 节课。

「Lua 中的递归」这节课中我会学到什么？

实现递归算法，并理解 Lua 的尾调用优化。 你通过在浏览器中直接运行的动手代码来练习 Lua Academy，全天候 AI 导师会在你学习这节课的过程中回答你的问题。

学习 Lua Academy 需要有经验吗？

无需任何先前经验。CoddyKit 上的 Lua Academy 课程适合初学者到高级学习者，你可以从这里开始或从头开始，按照自己的节奏学习。 这是第 4 节课，共 4 节。

「Lua 中的递归」课时需要多长时间？

大多数 CoddyKit 课程大约需要 5–10 分钟。每节课都很精短且互动，所以你能稳步进步，并在网页和应用中从离开的地方继续。

我能在这节 Lua Academy 课中编写并运行代码吗？

能。每节 Lua Academy 课都包含内置代码编辑器，你可以在浏览器中直接编写并运行真实代码，并获得即时 AI 反馈 — 无需本地设置。

此课程中的所有课时

  1. 定义和调用函数
  2. 多个返回值
  3. 可变参数和 ... 运算符
  4. Lua 中的递归
← 返回 Lua Academy