توابع بازگشتی در لوا

بازگشت چیست؟

بازگشت (Recursion) یعنی تابع خودش را صدا بزند. مثل آینه‌ای که روبه‌روی آینه دیگر است — اما با یک شرط توقف!

ساختار تابع بازگشتی

local function countdown(n)
  -- شرط توقف (پایه)
  if n == 0 then
    print("پایان!")
    return
  end

  -- کار این مرحله
  print(n)

  -- فراخوانی مجدد با مسئله کوچک‌تر
  countdown(n - 1)
end

countdown(5)
-- 5 4 3 2 1 پایان!

مثال کلاسیک: فاکتوریل

local function factorial(n)
  if n <= 1 then
    return 1   -- شرط توقف
  end
  return n * factorial(n - 1)
end

print(factorial(5))    -- 120
print(factorial(10))   -- 3628800

چطور کار می‌کند؟

factorial(5)
= 5 × factorial(4)
= 5 × 4 × factorial(3)
= 5 × 4 × 3 × factorial(2)
= 5 × 4 × 3 × 2 × factorial(1)
= 5 × 4 × 3 × 2 × 1
= 120

مثال کلاسیک: فیبوناچی

local function fib(n)
  if n <= 2 then
    return 1
  end
  return fib(n - 1) + fib(n - 2)
end

for i = 1, 8 do
  print("fib(" .. i .. ") = " .. fib(i))
end
-- 1, 1, 2, 3, 5, 8, 13, 21

بازگشت دمی (Tail Recursion)

وقتی فراخوانی بازگشتی آخرین کار تابع باشد، لوا آن را بهینه می‌کند (پشته پر نمی‌شود):

-- بازگشت دمی: امن برای n بزرگ
local function factorialTail(n, acc)
  acc = acc or 1
  if n <= 1 then
    return acc
  end
  return factorialTail(n - 1, n * acc)
end

print(factorialTail(20))   -- خیلی سریع!

بازگشت با جدول‌ها

-- شمارش عناصر تو در تو
local function deepCount(t)
  local count = 0
  for _, v in pairs(t) do
    if type(v) == "table" then
      count = count + deepCount(v)
    else
      count = count + 1
    end
  end
  return count
end

local data = {1, 2, {3, 4, {5}}, 6}
print(deepCount(data))   -- 6

بازگشت در برابر حلقه

هر بازگشتی را می‌توان با حلقه نوشت (و معمولاً سریع‌تر است):

-- با بازگشت
local function sumRec(n)
  if n == 0 then return 0 end
  return n + sumRec(n - 1)
end

-- با حلقه (سریع‌تر)
local function sumLoop(n)
  local total = 0
  for i = 1, n do
    total = total + i
  end
  return total
end

print(sumRec(10), sumLoop(10))   -- 55  55