468,491 Members | 1,950 Online
Bytes | Developer Community
New Post

Home Posts Topics Members FAQ

Post your question to a community of 468,491 developers. It's quick & easy.

Recursion

What's the secret to writing recursive functions that won't crash the
computer?

Aug 21 '06 #1
10 3177
MakeMineScotch wrote:
What's the secret to writing recursive functions that won't crash the
computer?
Make sure that you do not run out of memory???
Watch out for recursion to unlimited depth???
Aug 21 '06 #2
Sjouke Burry wrote:
MakeMineScotch wrote:
>What's the secret to writing recursive functions that won't crash the
computer?
Make sure that you do not run out of memory???
Watch out for recursion to unlimited depth???
Some recursive algorithms are just clever loops, so replacing them with a
real loop might change their performance and footprint.

The recursions that are not just clever loops, they are stack algorithms,
with a FIFO situation. Recursion borrows the system stack to implement this
latent data structure. Replacing the recursion with an explicit stack data
structure might change their performance and footprints.

All algorithms are trades-off; there's no single answer to the question!

--
Phlip
http://c2.com/cgi/wiki?ZeekLand <-- NOT a blog!!!
Aug 21 '06 #3
"MakeMineScotch" <ki********@dcs.qld.gov.auwrote in message
news:11*********************@75g2000cwc.googlegrou ps.com...
What's the secret to writing recursive functions that won't crash the
computer?
You have to make sure that the recursion can not be infinite. There has to
be a way to end the recursion. There has to be some condition when the
funtion does not call itself, this is usually when a variable is hit or
such.

A simple recursion function would be:
(note, untested code, may have bugs)

int RecursionTest( const int Depth )
{
if ( Depth >= 10 )
return 0;
else
return 1 + Add( Depth + 1 );
}

So that if Depth is greater than 10, it will not call itself, thus ending
the recursion.
Also, I have no idea what value this recursion function would actually call
if you did
int Val = RecursionTest( 0 );
It would return some number but I just did it as an example, not an actually
useful one.
Aug 21 '06 #4
set a condition....such as use loop
regards
<a href=www.gamestotal.com>free</a>
<a href=http://www.geocities.com/fiercy02>online</a>
<a href=http://unificationwars.esmartdesign.com/>online games</a>

Aug 21 '06 #5
MakeMineScotch wrote:
What's the secret to writing recursive functions that won't crash the
computer?
Making them tail call recursive and using a compiler that does
tail call optimizations.
Aug 21 '06 #6
Jim Langston schrieb:
"MakeMineScotch" <ki********@dcs.qld.gov.auwrote in message
news:11*********************@75g2000cwc.googlegrou ps.com...
>What's the secret to writing recursive functions that won't crash the
computer?

You have to make sure that the recursion can not be infinite. There has to
be a way to end the recursion. There has to be some condition when the
funtion does not call itself, this is usually when a variable is hit or
such.

A simple recursion function would be:
(note, untested code, may have bugs)

int RecursionTest( const int Depth )
{
if ( Depth >= 10 )
return 0;
else
return 1 + Add( Depth + 1 );
}
There is no recursion. You need to call RecursionTest() from
RecursionTest():

.....
else
return 1 + RecursionTest(Depth + 1);

>
So that if Depth is greater than 10, it will not call itself, thus ending
the recursion.
Also, I have no idea what value this recursion function would actually call
if you did
int Val = RecursionTest( 0 );
It would return some number but I just did it as an example, not an actually
useful one.
Well it's not that hard to figure out, isn't it:
(let R() be RecursionTest())

int val = R(0);
val = 1+R(1)
R(1) = 1 + R(2)
R(2) = 1 + R(3)
R(3) = 1 + R(4)
R(4) = 1 + R(5)
R(5) = 1 + R(6)
R(6) = 1 + R(7)
R(7) = 1 + R(8)
R(8) = 1 + R(9)
R(9) = 1 + R(10)
R(10) = 0

=>
val = 1 + R(1) + R(2) + R(3) + R(4) + R(5)
+ R(6) + R(7) + R(8) + R(9) + 0
= 10
/S

--
Stefan Naewe
stefan_DOT_naewe_AT_atlas_DOT_de
Aug 21 '06 #7

"Stefan Naewe" <pl****@nospam.netwrote in message
news:te***********@news01.atlas.de...
Jim Langston schrieb:
>"MakeMineScotch" <ki********@dcs.qld.gov.auwrote in message
news:11*********************@75g2000cwc.googlegro ups.com...
>>What's the secret to writing recursive functions that won't crash the
computer?

You have to make sure that the recursion can not be infinite. There has
to
be a way to end the recursion. There has to be some condition when the
funtion does not call itself, this is usually when a variable is hit or
such.

A simple recursion function would be:
(note, untested code, may have bugs)

int RecursionTest( const int Depth )
{
if ( Depth >= 10 )
return 0;
else
return 1 + Add( Depth + 1 );
}

There is no recursion. You need to call RecursionTest() from
RecursionTest():
Yes. My bad. When I originally typed this I called the function Add, then
thought that wasn't a good name and renamed it to RecursionTest, but forgot
to change the function call.
Aug 21 '06 #8
"Phlip" <ph******@yahoo.comwrote in message
news:CN*****************@newssvr29.news.prodigy.ne t...
The recursions that are not just clever loops, they are stack algorithms,
with a FIFO situation.
ITYM LIFO...

Philip

Aug 21 '06 #9
In article <11*********************@75g2000cwc.googlegroups.c om>,
ki********@dcs.qld.gov.au says...
What's the secret to writing recursive functions that won't crash the
computer?
Unfortunately, there's no (portable) way to guarantee this --
specifically, there's no portable way to find out the maximum stack
depth supported, and IIRC, neither the C or nor C++ standard provides
any specification (or even recommendation) of a minimum depth that must
be supported.

You can't do much that's guaranteed to be portable, so you have to
decide what kind of system you're targeting and act accordingly. If you
have to support embedded systems and such, you'll probably need to
research the capabilities of your specific target -- they vary quite
widely. For a typical desktop system, you can probably plan on having at
least a megabyte of stack space total for your program, and it's fairly
easy to estimate the size of your stack frame based on number of
parameters and local variables.

Most recursive functions that use a number of invocations that's linear
wrt the data being processed are also easy to convert to iterative
forms. The ones that are difficult to convert typically only use
logarithmic invocations to start with, so stack overflow is rarely a
problem except with code that's clearly buggy (e.g. has the terminating
condition mis-coded).

--
Later,
Jerry.

The universe is a figment of its own imagination.
Aug 21 '06 #10
Philip Potter wrote:
ITYM LIFO...
Da!

--
Phlip
http://c2.com/cgi/wiki?ZeekLand <-- NOT a blog!!!
Aug 21 '06 #11

This discussion thread is closed

Replies have been disabled for this discussion.

Similar topics

5 posts views Thread by Peri | last post: by
12 posts views Thread by da Vinci | last post: by
43 posts views Thread by Lorenzo Villari | last post: by
2 posts views Thread by Csaba Gabor | last post: by
75 posts views Thread by Sathyaish | last post: by
19 posts views Thread by Kay Schluehr | last post: by
18 posts views Thread by MTD | last post: by
13 posts views Thread by robert | last post: by
20 posts views Thread by athar.mirchi | last post: by
35 posts views Thread by Muzammil | last post: by
By using this site, you agree to our Privacy Policy and Terms of Use.