Velocity Reviews > chance of stack overflow

# 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..

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@
"Usenet is a strange place" - dmr 29 July 1999

asit
Guest
Posts: n/a

 12-02-2007
then what is the best recursion procedure..if we have to sort a
million integers

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@
"Usenet is a strange place" - dmr 29 July 1999

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>