Can recursion cause segmentation fault?

[weidongtom]

Hi,

I was trying to implement a higher order function in C, summation over
a range with a given function. And the summation function is then used
to define sum_cubes. The program works fine when VAR is below 30000 or
around that, but as soon as VAR is bigger, say 40000, or 50000, then I
receive a segmentation error. Can anyone tell me why this is
happening? Thanks in advance.

#include <stdio.h>
#define VAR 30000
double sum(double(*func)(double), double a, double(*next)(double),
double b, double *result){
/*summation over func from a to b as incremented by next*/
if(a > b)
return 0;
else{
*result += (*func)(a);
return sum(func, (*next)(a), next, b, result);
}
}

double inc(double n){
return (++n);
}

double cube(double n){
return n*n*n;
}

double sum_cubes(double a, double b){
double result = 0;
sum(&cube, a, &inc, b, &result);
return result;
}

int main(){
printf("sum_cubes(1, %d) = %d\n", VAR, sum_cubes(1, VAR));
return 0;
}

 

[Chris Dollin]

Hi,

I was trying to implement a higher order function in C, summation over
a range with a given function. And the summation function is then used
to define sum_cubes. The program works fine when VAR is below 30000 or
around that, but as soon as VAR is bigger, say 40000, or 50000, then I
receive a segmentation error. Can anyone tell me why this is
happening? Thanks in advance.

#include <stdio.h>
#define VAR 30000
double sum(double(*func)(double), double a, double(*next)(double),
double b, double *result){

Can't you give the variables better names than `a` and `b`?
`from` and `to`, for example?

/*summation over func from a to b as incremented by next*/
if(a > b)
return 0;
else{
*result += (*func)(a);

(You can write that as `func(a)` if you prefer. I do, but some
people want to make it explicit that they're calling through
an explicit function pointer.)

return sum(func, (*next)(a), next, b, result);

Why are you always returning `0`? If you're going to deliver
the result by side-effecting `*result`, why have a function
result at all -- conversely, why not return the answer at the
bottom of the recursion, rather than some integer?

}
}

You've probably blown the stack. Even though this code is
blatently tail-recursive, C compilers are not required to
optimise tail-calls of any kind. Since is /is/ so obviously
tail-recursive, it's easy to turn it into a loop.

double inc(double n){
return (++n);
}

Please, just `return n+1`. There's no point in side-effecting the
local variable `n`.

int main(){

Yay! `int main`! (That's approval, by the way.)

--
"It took a very long time, much longer than the most /Sector General/
generous estimates." - James White

Hewlett-Packard Limited registered office: Cain Road, Bracknell,
registered no: 690597 England Berks RG12 1HN

 

[Richard Heathfield]

(e-mail address removed) said:

Hi,

I was trying to implement a higher order function in C, summation over
a range with a given function. And the summation function is then used
to define sum_cubes. The program works fine when VAR is below 30000 or
around that, but as soon as VAR is bigger, say 40000, or 50000, then I
receive a segmentation error.

That is one legal outcome of passing a double to printf to match a %d
character. But it does sound very much as if you're blowing your
function stack.

If you must use recursion, consider splitting the problem into two parts
and recursing into each part separately. For example, you might deal
with a to (a+b)/2 in one half, and e+(a+b)/2 to b in the other half.
This means that instead of recursing VAR levels deep, you'll only be
recursing log2 VAR levels instead.