在递归函数中使用基础变量重要吗?

我正在学习递归,它非常难以理解。我发现一个非常常见的例子:

function factorial(N)
    local Value
    if N == 0 then
        Value = 1
    else
        Value = N * factorial(N - 1)
    end
    return Value
end
print(factorial(3))

N == 0 是基础案例。但是当我将其更改为 N == 1 时,结果仍然保持不变。_(它将打印出 6)_.

使用基础案例很重要吗?(会破坏或其他什么东西吗?)

使用 N == 0 (基础案例) 和 N == 1 有什么区别呢?

点赞
用户4984564
用户4984564

这只是一个巧合,因为 1 * 1 = 1,所以无论如何它都能工作。

但是考虑到边缘情况,即 N = 0,如果你检查 N == 1,那么你将进入 else 分支并计算 0 * factorial(-1),这将导致无限循环。

如果你直接调用 factorial(-1),那么两种情况都会发生,这就是为什么你应该使用 >0 进行检查(实际上将每个负值视为 0 并返回 1),或者添加另一个 if 条件,并在 N 为负数时引发错误。


编辑:正如另一个答案指出的那样,你的实现不是尾递归,这意味着它在每个递归函数调用中累积内存,直到完成或耗尽内存。

你可以使函数成为尾递归,这使得 Lua 能够将它视为一个几乎可以运行多长时间来计算其结果的普通循环:

local function factorial(n, acc)
   acc = acc or 1
   if n <= 0 then
      return acc
   else
      return factorial(n-1, acc*n)
   end
   return Value
end
print(factorial(3))

请注意,对于阶乘,你用尽栈内存比 Luas 数字数据类型溢出要花费更长的时间,在大约 21! 处。因此,使它成为尾递归只是训练自己编写更好的代码的问题。

2020-07-01 14:32:54
用户9922866
用户9922866

正如上面的答案和评论所指出的那样,在递归函数中必须有一个基本情况,否则就会形成无限循环。

此外,在您的阶乘函数的情况下,使用一个辅助函数来执行递归可能更有效,因此可以利用Lua的尾调用优化。由于Lua方便地允许本地函数,因此可以在阶乘函数的作用域内定义一个辅助函数。

请注意,此示例不适用于负数的阶乘。

-- 需要:n是大于或等于0的整数。
-- 效果:返回n的阶乘。
function fact(n)
    -- 实际执行递归的本地函数。
    local function fact_helper(n, i)
        -- 这是基本情况。
        if (i == 1) then
            return n
        end
        -- 利用尾调用。
        return fact_helper(n * i, i - 1)
    end
    -- 检查边缘情况,比如fact(0)和fact(1)。
    if ((n == 0) or (n == 1)) then
        return 1
    end
    return fact_helper(n, n - 1)
end
2020-07-01 17:18:25