Recursion

[MakeMineScotch]

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

[Sjouke Burry]

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???

[Phlip]

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!!!

[Jim Langston]

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

[ffairy2323]

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>

[Nils O. Selåsdal]

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.

[Stefan Naewe]

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

[Jim Langston]

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

[Philip Potter]

"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

[Jerry Coffin]

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.

[Phlip]

Philip Potter wrote:

ITYM LIFO...

Da!

--
Phlip
http://c2.com/cgi/wiki?ZeekLand <-- NOT a blog!!!