嵌套函数的效率如何？

我不知道 Lua，但在 Scala 中是非常常见的，在递归函数中用于确保尾递归优化：

def factorial(i: Int): Int = {
      @tailrec
     def fact(i: Int, accumulator: Int): Int = {
        if (i <= 1)
           accumulator
        else
           fact(i - 1, i * accumulator)
     }
     fact(i, 1)
  }

有关尾递归和递归的更多信息，请单击此处。

您写的方法造成任何低效率吗，因为每次调用外部方法时定义或创建了嵌套函数实例？

效率是一个广泛而复杂的话题。我假设你说的“低效”是指“每次调用该方法都有额外的开销”？

我只能代表 Scala，特别是针对 JVM 的版本来谈论，因为其他版本可能会有不同的行为。

我们可以将这个问题分为两个部分，具体取决于你的真正意图。

在 Scala 中，嵌套（局部）方法是一个词法作用域特性，这意味着它们可以访问外部方法的值，但是一旦我们生成字节码，它们就被定义在类级别上，就像普通的 Java 方法一样。

为了完整性，需要知道的是，Scala 还有函数值，它们是第一类公民，意味着你可以将它们传递给其他函数，然后会有一个分配开销，因为它们是用类实现的。

阶乘可以用尾递归的方式来编写，就像在你的例子中写的一样。Scala 编译器足够聪明，它会注意到你的方法是尾递归的，并将其转换为迭代循环，避免每次迭代的方法调用。如果可能，它还会尝试将factorial方法内联，避免额外的堆栈帧分配开销。

例如，考虑以下 Scala 中的阶乘实现：

def factorial(num: Int): Int = {
  @tailrec
  def fact(num: Int, acc: Int): Int = num match {
    case 0 => acc
    case n => fact(n - 1, acc * n)
  }

  fact(num, 1)
}

乍一看，我们有一个递归方法。让我们看看 JVM 字节码长什么样子：

private final int fact$1(int, int);
  Code:
   0: iload_1
   1: istore        4
   3: iload         4
   5: tableswitch   { // 0 to 0
                 0: 24
           default: 28
      }
  24: iload_2
  25: goto          41
  28: iload         4
  30: iconst_1
  31: isub
  32: iload_2
  33: iload         4
  35: imul
  36: istore_2
  37: istore_1
  38: goto          0
  41: ireturn

我们看到这里的递归变成了一个迭代循环（一个tableswitch和一个跳转指令）。

关于方法实例创建，如果我们的方法不是尾递归的，JVM 运行时将需要为每次调用解释它，直到C2 编译器发现它足够优秀，以便 JIT 编译它并在之后重复使用机器码的每个方法调用。

通常，除非发现该方法在您的热路径执行中，否则我会说这不应该让您担心，并且在对代码进行分析的过程中引发此问题。

总之，效率是一个非常复杂、应用特定的话题。从你提供的简化示例中，我认为我们没有足够的信息来告诉你这是你的用例所选择的最佳选项。我再次强调，如果这不是出现在你的分析器中，那就不必担心。

答案当然是取决于语言。

在 Scala 中，内部函数会被编译成它们似乎是在它们定义的函数的作用域之外的立场的方式。

这样，语言只允许您从词法作用域中调用它们，而不实际多次实例化函数。

我们可以通过编译两个变体来轻松测试这一点。

第一个是你的 Lua 代码的相当忠实的端口：

class Function1 {

  def factorial(n: Int): Int = {
    def _fac(n: Int, acc: Int): Int =
      if (n == 0)
        acc
      else
        _fac(n-1, acc * n)

    _fac(n, 1)
  }

}

第二个与之相差无几，但尾递归函数定义在 factorial 的范围之外：

class Function2 {

  def factorial(n: Int): Int = _fac(n, 1)

  private final def _fac(n: Int, acc: Int): Int =
    if (n == 0)
      acc
    else
      _fac(n-1, acc * n)

}

现在，我们可以使用 scalac 编译这两个类，然后使用 javap 查看编译器输出：

javap -p Function*.scala

这会产生以下输出：

Compiled from "Function1.scala"
public class Function1 {
  public int factorial(int);
  private final int _fac$1(int, int);
  public Function1();
}
Compiled from "Function2.scala"
public class Function2 {
  public int factorial(int);
  private final int _fac(int, int);
  public Function2();
}

我添加了 private final 关键字以最小化两者之间的差异，但需要注意的主要是在两种情况下都会在类级别上出现定义，而内部函数会自动定义为 private 和 final，并带有小的修饰以确保没有命名类（例如，如果您在两个不同函数的内部定义了一个名为 loop 的内部函数）。

不确定 Lua 或其他语言，但我至少可以期望大多数编译语言采用类似的方法。

让我们用 Lua 进行带/不带嵌套函数的基准测试。

变体1（在每次调用时创建内部函数对象）

local function factorial1(n)
   local function _fac1(n, acc)
      if n == 0 then
         return acc
      else
         return _fac1(n-1, acc * n)
      end
   end

   return _fac1(n, 1)
end

变体2（函数不嵌套）

local function _fac2(n, acc)
   if n == 0 then
      return acc
   else
      return _fac2(n-1, acc * n)
   end
end

local function factorial2(n)
   return _fac2(n, 1)
end

基准测试代码（计算12！，重复1000万次，并显示使用的CPU时间（秒））：

local N = 1e7

local start_time = os.clock()
for j = 1, N do
   factorial1(12)
end
print("CPU time of factorial1 = ", os.clock() - start_time)

local start_time = os.clock()
for j = 1, N do
   factorial2(12)
end
print("CPU time of factorial2 = ", os.clock() - start_time)

Lua 5.3解释器输出

CPU time of factorial1 = 8.237
CPU time of factorial2 = 6.074

LuaJIT（JIT编译器）输出

CPU time of factorial1 = 1.493
CPU time of factorial2 = 0.141

是的（或曾经是的），从Lua的努力可以证明，当执行多次函数定义的过程中，Lua尝试重用函数值。

Lua 5.2变更

函数值之间的相等性已经更改。现在，函数定义可能不会创建新值，如果新函数没有观察到差异，则可以重用先前的某些值。

既然你已经编码（假设是Lua），并且把函数分配给了一个在更高范围中声明的全局变量或本地变量，你可以自己编写短路代码（假设没有其他代码将其设置为除了nil或false之外的任何值）：

function factorial(n)
  _fac = _fac or function (n, acc)
  …
  end
  …
end