Is my function here a tail recursion? If so why/ why not? I have some trouble grasping the concept so any help is much appreciated.

struct link 
{
  int value; //data    
  link_t *next; //link
};

struct list
{
    link_t *first;
    link_t *last;
};


int list_size_count(link_t *first, int acc)
{
  if (first != NULL)
  {
    return (acc   list_size_count((first->next), 1));
  }
  return acc;
}

int linked_list_size(list_t *list)
{
  return list_size_count((list->first),0);
}

CodePudding user response：

For a function to be tail recursive, the recursive call must be its last action. In your code, the last thing the function does is adding two values, so list_size_count() is not tail recursive.

int list_size_count(link_t *first, int acc)
{
  if (first != NULL)
  {
    return (acc   list_size_count((first->next), 1));
  }
  return acc;
}

Here is how to make it tail recursive:

int list_size_count(link_t *first, int acc)
{
  if(first != NULL)
  {
    return list_size_count(first->next, acc   1);
  }

  return acc;
}

CodePudding user response：

Is my function here a tail recursion?

No it's not.

This line

return (acc   list_size_count((first->next), 1));

includes an add operation after the recursive call returns, i.e. an add of acc and whatever the recursive call returns. Consequently it's not a tail recursion.

But it's easy to turn into tail recursion. Simply change the above line to:

  acc;
return list_size_count((first->next), acc);

Here acc is incremented first and passed as argument to the recursive function and the result of the recursive call is used directly in the return statement.

Now there is no operation after the recursive call. Consequently it's tail recursion.

CodePudding user response：

If the final action of a routine is to call another routine, it is called a tail call. An example is a routine, say a routine named g, that ends with return f(x);. The straightforward way to compile this code is:

• Pass the argument x by copying it to the designated place to pass an argument.
• Execute a subroutine call instruction to call f.
• Clean up the stack frame (as by restoring the stack pointer to the value it had when this routine started executing) and execute a return instruction.

Because this is the last thing the routine g is going to do, we do not need f to return to g. Instead of calling it, we can jump to it:

• Copy x to where an argument is passed.
• Execute a branch instruction to jump to f.

Then f will execute, clean up the stack frame we are currently in, and execute a return instruction. That will return to g’s caller, as if g had executed a return instruction. We get the same effect from these instructions as from the earlier instructions but with less work.

(There are further details not shown here. For this to work, the rules about managing stack frames have to allow f to clean up the stack frame of g, even though f may also establish its own context on the stack.)

If f and g are the same routine, this is called tail recursion.

Note that, in this example, f and g must return the same type of data. If f returns a float and g returns an int, then, when g contains return f(x);, calling f is not actually the last thing g does. There is an automatic conversion from float to int in the return statement, so that would not be a tail call.

A tail call just has to be the last action of a routine; it does not have to be the last source code in a routine. If return f(x); appears anywhere in the routine (and the types match), that is a tail call, and it can be replaced by a branch (if the stack management rules permit). Also, if the return type of g is void, then f(x); return; anywhere in the routine is a tail call, and f(x); at the end of the routine is a tail call.

In your routine linked_list_size, return list_size_count((list->first),0); is a tail call, but it is not tail recursion.

In your routine list_size_count, there is no tail call because, in return (acc list_size_count((first->next), 1));, the is executed after the call to list_size_count. You can make it a tail call, and tail recursion, by rewriting it to:

return list_size_count(first->next, acc 1);