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

2013-6-25 14:31:52
收藏：0
阅读：121
评论：2

为了学习 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 中编写它来避免这些副作用？

点赞
用户2458769
用户2458769

如果你想要一个全局变量，可以尝试以下代码，但会有副作用：

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);
      }
   }
2013-06-25 13:33:00
用户317562
用户317562

如 Shar 在上面指出的那样，将 lua 代码直接转换为 C 的代码是：

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

在上限为 100 的情况下，除非您使用的是非常小的嵌入式系统，否则堆栈使用不会成为问题。然而，在 C 中没有保证 C 编译器会进行尾调用优化（就像您所说的那样，“Lua 聪明地在再次调用后退出函数，以避免创建堆栈嵌套函数的巨大堆栈”）。

对于这样一个简单的例子，许多编译器实际上会进行尾调用优化，但是你不应该使用 if(a == 1000000000) 并依赖它。如果你这样做，你可能会有一个在“Release”优化的版本中运行正常但在“Debug”版本中崩溃的程序。

所以，如果您知道将有很多递归，可以自己进行优化：

int increment(int a)
{
  for(;;)
  {
    if(a == 100)
      return a;
    else
      a = a + 1;
  }
}
// 然后“整理一下”
int increment(int a)
{
  while (a != 100)
  {
    a = a + 1;
  }
  return a;
}
2013-06-28 12:39:02

作者:

用户2395058

用户2395058
推荐文章