Segmentation fault in a recursive approach to compute factorial(n)%m

Question

I am trying to compute n! % m using recursion in C. This is the code I am using

#include<stdio.h>
#define m 1000000007

long long int fact(long long int n) {
    if(n == 1)
        return (1);
    long long int n2 = (long long int)(fact(n-1));
    long long int k = (n*n2)%m;
    return k;
}

int main() {
    printf("%lld",fact(1000000));
}

This program gives SEGMENTATION FAULT , but if I replace the fact function with an iterative approach then program prints correct answer.The iterative fact function is

long long int fact(long long int n){
    long long int k =1;
    long long int i;
    for(i = n;i>1;i--)
        k = (k*i)%m;
    return k; 
}

So why the iterative approach works but the recursive approach is failing?

Answer 1

If your C compiler optimizes tail calls you can rewrite your recursive function to a tail recursive one:

long long int fact_aux(long long int n, long long int acc) {
    if(n <= 1)
        return acc;
    return fact_aux(n-1, (n * acc)%m);
}

long long int fact(long long int n) {
     return fact_aux(n, 1);
}

Note that the C standard doesn't require TCO so you have no guarantee this will be as effective as a loop. GCC does it.