why i get segmentation fault, where is the bug?

demosthenesk

unread,

May 21, 2012, 6:50:28 AM5/21/12

to

hi to all,
i am a newbie to C++ and i want some help if you could ...

i try to implement a recursive linera search algorithm for learning
purposes but i get segmentation fault.
here is the code.

the problem appears when ULLI searchKey gets big values like 999999.
for small values like 254 the program works.

--------------------------------------------------------
#include <iostream>
using namespace std;
typedef unsigned long long int ULLI;

//prototypes
ULLI RecursiveLinearSearch(const ULLI *, ULLI, ULLI, ULLI);

int main()
{
const ULLI arraySize = 999999999; // size of array a
ULLI * a;
a = new ULLI [arraySize];
ULLI searchKey = 999999; // value to locate in array a
int element;

for ( ULLI i = 0; i < arraySize; ++i )
a[ i ] = i; // create some data

element = RecursiveLinearSearch( a, searchKey, 0, arraySize - 1 );

// display results
if ( element != -1 )
cout << "Found value in element " << element << endl;
else
cout << "Value not found" << endl;

return 0;
}

/
*~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
~ Search Algorithms ~
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~*/
// perform a recursive linear search on the data
ULLI RecursiveLinearSearch(const ULLI * array, ULLI key, ULLI low,
ULLI high )
{
// search array for key
if ( array[ low ] == key )
return low;
else if ( low == high )
return -1;
else
return RecursiveLinearSearch( array, key, low + 1, high );
} // end function recursiveLinearSearch

--------------------------------------------------------

Ian Collins

unread,

May 21, 2012, 6:58:22 AM5/21/12

to

On 05/21/12 10:50 PM, demosthenesk wrote:
> hi to all,
> i am a newbie to C++ and i want some help if you could ...
>
> i try to implement a recursive linera search algorithm for learning
> purposes but i get segmentation fault.
> here is the code.
>
> the problem appears when ULLI searchKey gets big values like 999999.
> for small values like 254 the program works.

Odds are you are running out of stack (too many recursions) or running
out of heap (too many big arrays). Running under a debugger should show
you which one.

> --------------------------------------------------------
> #include<iostream>
> using namespace std;
> typedef unsigned long long int ULLI;

Use uint64_t from <stdint.h> instead.

--
Ian Collins

Juha Nieminen

unread,

May 21, 2012, 11:59:01 AM5/21/12

to

Ian Collins <ian-...@hotmail.com> wrote:
>> typedef unsigned long long int ULLI;
>
> Use uint64_t from <stdint.h> instead.

Why? IIRC the standard guarantees that long long will be at least
64-bit.

Ian Collins

unread,

May 21, 2012, 3:28:34 PM5/21/12

to

Because it's a standard typedef and it doesn't look like a macro!

--
Ian Collins

Paavo Helde

unread,

May 21, 2012, 4:36:31 PM5/21/12

to

demosthenesk <demost...@gmail.com> wrote in
news:46f41353-0df7-480b...@z19g2000vbe.googlegroups.com:

> hi to all,
> i am a newbie to C++ and i want some help if you could ...
>
> i try to implement a recursive linera search algorithm for learning
> purposes but i get segmentation fault.
> here is the code.
>
> the problem appears when ULLI searchKey gets big values like 999999.
> for small values like 254 the program works.

[...]

> ULLI RecursiveLinearSearch(const ULLI * array, ULLI key, ULLI low,
> ULLI high )

[...]

> return RecursiveLinearSearch( array, key, low + 1, high );
> } // end function recursiveLinearSearch

The parameters for RecursiveLinearSearch() take ca 32 bytes, not even
accounting for any other function call overhead. Recursing 1 million
times as you do makes it ca 32 MB. This is way more than the default size
of stack segment in typical implementations (around 4 or 8MB in 64-bit
implementations), so there is no wonder you get segfaults.

C++ is just not meant for so heavy recursion, hundreds are OK, millions
are not. You need to redesign your algorithm as a loop-based one or use
some other (functional) language (which would make this transformation to
a non-recursive algorithm behind the scenes for you, incidentally). There
is just no reasonable way to do a million recursions in C++.

hth
Paavo

Old Wolf

unread,

May 28, 2012, 6:39:37 AM5/28/12

to

On May 21, 10:50 pm, demosthenesk <demosthen...@gmail.com> wrote:
> const ULLI arraySize = 999999999; // size of array a
> ULLI * a;
> a = new ULLI [arraySize];

There might be not enough memory for this allocation,
it would be prudent to check it.

Maybe something like:
try
{

a = new ULLI[arraySize];
}

catch( std::exception &e )
{
std::cerr << "Unable to allocate 'a': " << e.what() << std::endl;
return 1;
}