Рекурсия в Lua
Реализуйте рекурсивные алгоритмы и изучите оптимизацию хвостовых вызовов в Lua.
«Рекурсия в Lua» — бесплатный урок Lua Academy на CoddyKit. Это урок 4 из 4. Ты можешь прочитать весь урок бесплатно ниже — а потом практиковать его прямо в браузере с встроенным редактором кода и ИИ-репетитором 24/7. Это часть пути обучения 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» бесплатно доступен здесь в веб-версии. Чтобы практиковать его интерактивно (встроенный редактор кода и ИИ-репетитор 24/7) и разблокировать остальной курс Lua Academy, подпишись на CoddyKit PRO. Курс Lua Academy содержит 4 уроков всего.
Чему я научусь в уроке «Рекурсия в Lua»?
Реализуйте рекурсивные алгоритмы и изучите оптимизацию хвостовых вызовов в Lua. Ты практикуешь Lua Academy с помощью реального кода, который запускаешь прямо в браузере, и ИИ-репетитор 24/7 отвечает на твои вопросы во время урока.
Нужен ли мне опыт, чтобы начать Lua Academy?
Предыдущий опыт не требуется. Lua Academy на CoddyKit структурирован для всех уровней — от новичков до продвинутых, поэтому ты можешь начать отсюда или с самого начала и учиться в своем темпе. Это урок 4 из 4.
Сколько времени занимает урок «Рекурсия в Lua»?
Большинство уроков CoddyKit занимают около 5–10 минут. Каждый из них компактный и интерактивный, поэтому ты постоянно делаешь прогресс и продолжаешь с того же места в веб-версии и приложении.
Можно ли писать и запускать код в этом уроке Lua Academy?
Да. Каждый урок Lua Academy включает встроенный редактор кода, поэтому ты пишешь и запускаешь реальный код прямо в браузере и получаешь моментальную обратную связь от AI — локальная установка не требуется.
Все уроки этого курса
- Определение и вызов функций
- Несколько возвращаемых значений
- Переменное число аргументов и оператор ...
- Рекурсия в Lua