Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > C Programming > chance of stack overflow

Reply
Thread Tools

chance of stack overflow

 
 
asit
Guest
Posts: n/a
 
      12-02-2007
we kno during call of a subroutine, the address of next
instruction( from which the execution is supposed to start after the
subroutine is executed ) is stored in stack. in case of recursion
(e.g. we are sorting an array having length one million using heap
sort), we have to call a particular subroutine thousands time. Is
their any chance of stack overflow ?? if yes how can we avoid ??

here we have no choice other than subroutine..
 
Reply With Quote
 
 
 
 
Richard Heathfield
Guest
Posts: n/a
 
      12-02-2007
asit said:

> we kno during call of a subroutine, the address of next
> instruction( from which the execution is supposed to start after the
> subroutine is executed ) is stored in stack.


We don't actually know that, because the C Standard doesn't guarantee it,
but it is certainly true that some systems work in that way.

> in case of recursion
> (e.g. we are sorting an array having length one million using heap
> sort), we have to call a particular subroutine thousands time. Is
> their any chance of stack overflow ??


It's unlikely. If you're sorting a million items in a recursive O(n log n)
algorithm, you're unlikely to have to recurse more than twenty calls deep,
and that's really no big deal. (2^20 == 1048576)

--
Richard Heathfield <http://www.cpax.org.uk>
Email: -http://www. +rjh@
Google users: <http://www.cpax.org.uk/prg/writings/googly.php>
"Usenet is a strange place" - dmr 29 July 1999
 
Reply With Quote
 
 
 
 
asit
Guest
Posts: n/a
 
      12-02-2007
then what is the best recursion procedure..if we have to sort a
million integers
 
Reply With Quote
 
Richard Heathfield
Guest
Posts: n/a
 
      12-02-2007
asit said:

> then what is the best recursion procedure..if we have to sort a
> million integers


It depends on the range of the integers. For example, if the inputs were
all in the range 0 to 9 - single digits - I would give one answer, and if
the inputs were bignums of arbitrary length, I'd give a very different
answer. And if, as is likely, the truth is somewhere between those two
outliers, I'd give a different answer again.

--
Richard Heathfield <http://www.cpax.org.uk>
Email: -http://www. +rjh@
Google users: <http://www.cpax.org.uk/prg/writings/googly.php>
"Usenet is a strange place" - dmr 29 July 1999
 
Reply With Quote
 
Martin Ambuhl
Guest
Posts: n/a
 
      12-02-2007
asit wrote:
> we kno during call of a subroutine, the address of next
> instruction( from which the execution is supposed to start after the
> subroutine is executed ) is stored in stack.


We know (note spelling) no such thing. There are many ways for
subroutines to be supplied with the location to which returns should
lead, and many ways for subroutines to use such information.

Any question based upon your false premise is useless. However,

> in case of recursion
> (e.g. we are sorting an array having length one million using heap
> sort), we have to call a particular subroutine thousands time. Is
> their any chance of stack overflow ?? if yes how can we avoid ??


Unless you somehow have access to an infinite memory machine, it is
obvious that any unrestrained use of a stack carries with it the chance
of overflowing that stack. It doesn't matter what use you put that
stack to. There is no automatic way of avoiding violating the limits of
any region of memory. As to which precautions you should take, that
is obviously intimately bound to your implementation. Knowledge of your
implementation and the skills to use that knowledge have nothing to do
with the C programming language and are off-topic in <news:comp.lang.c>

 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
C/C++ compilers have one stack for local variables and return addresses and then another stack for array allocations on the stack. Casey Hawthorne C Programming 3 11-01-2009 08:23 PM
Why stack overflow with such a small stack? Kenneth McDonald Ruby 7 09-01-2007 04:21 AM
SDM Java stack overflow Art Cisco 1 02-18-2006 07:34 PM
smart navigation gives stack overflow Mr m?ll ASP .Net 2 10-16-2004 01:09 PM
Stack overflow exception =?Utf-8?B?amJpeEBuZXdzZ3JvdXBzLm5vc3BhbQ==?= ASP .Net 5 04-22-2004 04:48 AM



Advertisments