How exactly does tail recursion work?

c algorithm recursion tail-recursion
Alan Coromano picture Alan Coromano · Mar 20, 2013 · Viewed 17.6k times · Source

I almost understand how tail recursion works and the difference between it and a normal recursion. I only don't understand why it doesn't require stack to remember its return address.

// tail recursion
int fac_times (int n, int acc) {
    if (n == 0) return acc;
    else return fac_times(n - 1, acc * n);
}

int factorial (int n) {
    return fac_times (n, 1);
}

// normal recursion
int factorial (int n) {
    if (n == 0) return 1;
    else return n * factorial(n - 1);
}

There is nothing to do after calling a function itself in a tail recursion function but it doesn't make sense for me.

Answer

Alexey Frunze picture Alexey Frunze · Mar 20, 2013

The compiler is simply able to transform this

int fac_times (int n, int acc) {
    if (n == 0) return acc;
    else return fac_times(n - 1, acc * n);
}

into something like this:

int fac_times (int n, int acc) {
label:
    if (n == 0) return acc;
    acc *= n--;
    goto label;
}

Related questions

Linked list recursive reverse

I was looking at the code below from stanford library: void recursiveReverse(struct node** head_ref) { struct node* first; struct node* rest; /* empty list */ if (*head_ref == NULL) return; /* suppose first = {1, 2, 3}, rest = {2, 3} */ first = *head_ref; rest = first->next; /* List …

Read More
Maximum Subarray: Divide and Conquer

Disclaimer: this is for an assignment. I am not asking for explicit code, only enough help to understand the algorithm involved so that I might fix the errors in my code. Okay, so you're probably familiar with the maximum subarray …

Read More
Generating all distinct partitions of a number

I am trying to write a C code to generate all possible partitions (into 2 or more parts) with distinct elements of a given number. The sum of all the numbers of a given partition should be equal to the given …

Read More