how to translate recursive function in Lua to C

Question

In an effort to learn C programming, I'm attempting to translate some Lua Code into C. I know C is not considered a "functional" language in the same vein as Lua, but I want to know how/if it's possible. Lua Code:

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

In this code, Lua cleverly exits the function after calling it again to avoid creating a huge stack of nested functions.

Is there a method for this sort of recursion in C that exits a function before calling it again, to avoid forming a large group of nested functions?

I understand functions can be used in this way to avoid side effects; How can I write this in C to avoid them as well?

Answer 1

Try this code if you want a global, but there is side effect :

int a;

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

Prefer to use if you don't want side effect, and this solution DO NOT stack lot of function, because you call your function at the last statement.

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

For example this one create stack of function :

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

Answer 2

As Shar has pointed out above, the straight-forward translation of the lua code to C is:

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

For going up to 100, stack usage is not going to be a problem unless you are on a very small embedded system. However, there is no guarantee in C that a C compiler will do tail call optimization (which is, as you put it, the fact that "Lua cleverly exits the function after calling it again to avoid creating a huge stack of nested function").

For a simple example such as this, many compilers will actually do the tail call optimization, but it is a bad idea to use if(a == 1000000000) and rely on it. If you do that, you will probably have a program that works in "Release" optimized builds, but crashes in "Debug" builds.

So, if you know that there will be a lot of recursion, you can do the optimization yourself:

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;
}