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?

Looks like you are overflowing the call stack. Trying doing `ulimit -s unlimited` to increase the stack size. — David G, Sep 05 '14 at 22:21
The maximum height of your call stack is less than the maximum value of your `long long int i`. — Beta, Sep 05 '14 at 22:23

score 4 · Answer 1 · answered Sep 05 '14 at 22:21

4

try gdb, but likely its because you are reaching your max recursion depth, in other words running out of "memory" either literally or based on current rule sets for your os.

answered Sep 05 '14 at 22:21

cure

2,588
1
17
25

score 2 · Accepted Answer · edited May 23 '17 at 12:24

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.

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

2 Answers2