Segmentation fault in a massively recursive function

Question

I have a function that calls itself a near infinite amount of times, but it does have an end. It calculates the mathematical formula (in TeX):

When x<a:

g_{a}(x)=1

When x>=a:

g_{a}(x)=g_{a}(x-1)+g_a(x-a)

Here is my code(c++):

#include <iostream>
#include <math.h>
#include <stdio.h>
#include <cmath>
using namespace std;
double g( double a, double x){
    if (x>=a) return (g(a,x-1)+g(a,x-a));
    else if (x<a) return 1;
    return 0;
}
int main(){cout << g(sqrt(10000019),10000019);}

I call the function with g(sqrt(10000019),10000019); How do I stop the SEGFAULT?

And also, can't you post a [MCVE](http://stackoverflow.com/help/mcve)? — Fabio says Reinstate Monica, Oct 07 '15 at 17:03
BTW it is Ackermann_function, am I correct?? if yes then I doubt you can stop SEGFAULT. — g-217, Oct 07 '15 at 17:03
@Lightness erm... no? When I say near infinite, I sorta meant its overflowing my stack. — Kaiden Prince, Oct 07 '15 at 17:13
@KaidenPrince see if this makes sense ... http://stackoverflow.com/questions/10742322/how-to-rewrite-ackermann-function-in-non-recursive-style — g-217, Oct 07 '15 at 17:18
@KaidenPrince The function is complete, but a real MCVE also includes the `main()` function, and the #included headers, and so on. So that we can copy it, paste it into an IDE (even an online one), and see the error. By the way, including `main()` is important because then we can see the call to the function that is leading to your problem. At the beginning you hadn't included it... Now we have everything (I think), but we still have to put all the pieces together. If **you** did that,we would be able to focus directly on the problem. — Fabio says Reinstate Monica, Oct 07 '15 at 17:21
@GautamJha Brain overload... I am not a very good programmer... — Kaiden Prince, Oct 07 '15 at 17:26

score 2 · Answer 1 · answered Oct 07 '15 at 17:06

I suspect your seg-fault was from running out of stack space.

You can limit/unlimit how big your stack space is (on Linux at least) using the limit command from tcsh.

 % limit 
cputime      unlimited
filesize     unlimited
datasize     unlimited
stacksize    10240 kbytes
coredumpsize 0 kbytes
memoryuse    unlimited
vmemoryuse   unlimited
descriptors  4096 
memorylocked 64 kbytes
maxproc      1024

You can then unlimit your stacksize

% unlimit stacksize
% limit

cputime      unlimited
filesize     unlimited
datasize     unlimited
stacksize    unlimited
coredumpsize 0 kbytes
memoryuse    unlimited
vmemoryuse   unlimited
descriptors  4096 
memorylocked 64 kbytes
maxproc      1024

And give it another try.

Yes, but he may make it far enough for his purposes. Another solution would to cache/memoize small values so it doesn't ave to do as much recursion. — rts1, Oct 07 '15 at 17:11

score 1 · Answer 2 · answered Oct 07 '15 at 17:11

1

I have a function that calls itself a near infinite amount of times, but it does have an end.

Do you have a near infinite amount of stack memory?

If not (the likely scenario), you are going to smash your stack in no time. A segmentation fault is a clear sign of that here.

I'd avoid the recursion altogether.

answered Oct 07 '15 at 17:11

Lightness Races in Orbit

378,754
76
643
1,055

How would I convert this to iteration then? – Kaiden Prince Oct 07 '15 at 17:15
@KaidenPrince: With your fingers...? I don't understand your question. – Lightness Races in Orbit Oct 07 '15 at 17:15
I don't really know how to convert it, or else I would of. – Kaiden Prince Oct 07 '15 at 17:16
You can also try converting it into tail recursion. Then the optimizer will hit it and turn it into iteration for you. – Edward Strange Oct 07 '15 at 17:24
@CrazyEddie Will try. Post an update later. GCC will optimize this? – Kaiden Prince Oct 07 '15 at 17:29
@KaidenPrince - it should optimize *tail* recursion. This means that no operation can happen after the recursive call. The addition you do in your return statement is such an operation. Converting to tail recursion often involves passing the result as an accumulator parameter into the recursive call. See: http://stackoverflow.com/questions/15537432/convert-recursion-to-tail-recursion – Edward Strange Oct 07 '15 at 17:33
I seem unable to understand how to convert this to tail recursion. – Kaiden Prince Oct 08 '15 at 15:24

Segmentation fault in a massively recursive function

2 Answers2

Linked