Is there limitation for recursion?

Question

I am testing recursion, however when I have an array with more than 150000 elements segmentation error occurs. What can be the problem?

#include <iostream> using namespace std; void init ( float a[] , long int n ); float standard ( float a[] , long int n , long int i ); int main() { long int n = 1000000; float *a = new float[n]; init ( a , n ); cout.precision ( 30 ); cout << "I got here." << endl; cout << "Standard sum= " << standard ( a , 0 , n - 1 ) << endl; delete [] a; return 0; } void init ( float a[] , long int n ) { for (long int i = 0 ; i < n ; i++ ) { a[i] = 1. / ( i + 1. ); } } float standard ( float a[] , long int i , long int n ) { if ( i <= n ) return a[i] + standard ( a , i + 1 , n ); return 0; }

In any case, trhat smells more of stack overflow instead of segmentation fault. — deviantfan
– deviantfan, Commented Dec 4, 2014 at 11:50
I am getting the following result: I got here. Segmentation fault (core dumped) — Mokus
– Mokus, Commented Dec 4, 2014 at 11:51

eerorika · Accepted Answer · 2014-12-04 12:24:14Z

As an expansion to MicroVirus' correct answer, here is an example of tail recursive version of your algorithm:

float standard_recursion(float* a, long i, long n, long result) { if(i > n) return result; return standard_recursion(a, i + 1, n, result + a[i]); } float standard(float* a, long i, long n ) { return standard_recursion(a, i, n, 0); }

This should run if the compiler does tail call optimization (I tested on g++ -O2). However, since the functionality depends on the compiler optimization, I would recommend to avoid deep recursion entirely and opt for iterative solution.

MicroVirus · Accepted Answer · 2014-12-04 11:52:33Z

You are most likely running out of stack space in your recursive function standard, which recurses with a depth of n, and tail-call optimisation is probably not enabled here.

So, to answer the question in your title: Yes, there is a limit to recursion, and usually it's the available stack space.

MateuszZawadzki · Accepted Answer · 2014-12-04 11:44:22Z

0

Probably you are out of memory on heap. Also if you got 16bit int, there could be a problem with iterations. Better use int32_t i instead of int i. Same with n.

answered Dec 4, 2014 at 11:44

MateuszZawadzki

1492 bronze badges

5 Comments

eerorika Over a year ago

I doubt he's running out of heap space. 150000 floats is about half a megabyte.

MicroVirus Over a year ago

No reason to use use explicit-bitsize types here (i.e. the int32_t): stick to int, or else go for long, unless the width of the type needs to be fixed to some exact number.

slebetman Over a year ago

@user2079303: It wouldn't be 150000 floats. It would be 150000 stack frames - the sum of all local variables + the return pointer

slebetman Over a year ago

OK. I see now. This answer is a partial answer that should be read with MicroVirus's answer.

eerorika Over a year ago

@LokiAstari yes, those stack frames probably consume more memory. Possibly not enough to fill the heap though. But as the name implies, stack frames are stored on the stack and that's where he's run out of memory - not on the heap. Maximum stack size does not grow according to use, it's limit is set on compilation.

Collectives™ on Stack Overflow

Is there limitation for recursion?

3 Answers 3

Comments

Comments

5 Comments

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

Comments

Comments

5 Comments

Related