如何将Lua中的递归函数翻译成C语言

Question

为了学习C编程，我试图将一些Lua代码翻译成C。我知道C不像Lua那样被认为是“函数式”语言，但我想知道它是否可能。Lua代码：

function Increment(a)
a = a + 1
if a == 100 then return 0
else return Increment(a) end end

在这段代码中，Lua聪明地在再次调用函数后退出函数，以避免创建一个巨大的嵌套函数堆栈。

在C语言中，是否有一种递归方法可以在再次调用函数之前退出函数，以避免形成大量嵌套函数？

我知道函数可以用来避免副作用；如何在C语言中编写以避免副作用呢？

- ridthyself

---

你需要使用 a == 10 而不是 a = 10。 - lhf

你是说Lua支持尾调用而C不支持吗？ - lhf

@lhf的修改已经完成，感谢您的注释。 - ridthyself

Answer 1

如果您想要一个全局变量，可以尝试这段代码，但是会产生副作用：

int a;

int increment()
{
    a = a + 1;
    if (a == 100)
        return 0;
    else
        return increment();
}

如果您不想产生副作用，建议使用这种方法。此解决方案不会堆叠大量函数，因为您在最后一个语句中调用函数。

int increment(int a)
{
  if (a == 100)
     return a;
  else
     return increment(a + 1);
}

例如，这个例子创建了一个函数堆栈：

    int increment(int a)
    {
      if (a == 100)
         return a;
      else
      {
         a = increment(a);
         return (a + 1);
      }
   }

- Shar

---

我修改了我的代码，使用全局变量实现了它，但是我认为这不是C语言中的一个好习惯，请小心使用。 - Shar

@etothepowerofx，在Lua中的函数参数是一个本地变量，与C语言相同。 - lhf

@lhf 我明白了。这就是为什么人们声称函数可以消除副作用的原因吗？因为在函数运行时实际值保持不变？ - ridthyself

在我的例子中，你有副作用是因为你做了 "a = a + 1"。我的第一个解决方案是使用返回 increment(a + 1);，没有副作用。（而我认为你的 Lua 代码有副作用）。 - Shar

@Shar 谢谢你的帮助！这是一个非常简单的例子，我很感激。 - ridthyself

Answer 2

正如Shar在上面指出的那样，将lua代码直接翻译为C的方法是：

int increment(int a)
{
  if (a == 100)
     return a;
  else
     return increment(a + 1);
}

对于递归层数不超过100的情况，除非你在一个非常小的嵌入式系统上，否则堆栈使用量不会成为问题。然而，在C语言中并没有保证C编译器会进行尾调用优化（即“Lua巧妙地在再次调用函数后退出函数，以避免创建大量嵌套函数的堆栈”）。

对于像这样的简单示例，许多编译器实际上会进行尾调用优化，但是使用if(a == 1000000000)并依赖它是一个坏主意。如果你这样做，你可能会有一个在“发布”优化构建中工作正常但在“调试”构建中崩溃的程序。

因此，如果你知道将会有很多递归，你可以自己进行优化：

int increment(int a)
{
  for(;;)
  {
    if(a == 100)
      return a;
    else
      a = a + 1;
  }
}
// and then "clean it up":
int increment(int a)
{
  while (a != 100)
  {
    a = a + 1;
  }
  return a;
}

- wolfgang