Recursion

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

re: Recursion

MakeMineScotch wrote:Make sure that you do not run out of memory???
Watch out for recursion to unlimited depth???

re: Recursion

Sjouke Burry wrote:
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!!!

re: Recursion

"MakeMineScotch" <kim.slater@dcs.qld.gov.auwrote in message
news:1156133927.260732.32300@75g2000cwc.googlegrou ps.com...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.

re: Recursion

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>

re: Recursion

MakeMineScotch wrote:Making them tail call recursive and using a compiler that does
tail call optimizations.

re: Recursion

Jim Langston schrieb:There is no recursion. You need to call RecursionTest() from
RecursionTest():

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

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

re: Recursion

"Stefan Naewe" <please@nospam.netwrote in message
news:terbce-vkm.ln@news01.atlas.de...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.

re: Recursion

"Phlip" <phlipcpp@yahoo.comwrote in message
news:CNaGg.9673$%j7.9464@newssvr29.news.prodigy.ne t...ITYM LIFO...

Philip

re: Recursion

In article <1156133927.260732.32300@75g2000cwc.googlegroups.c om>,
kim.slater@dcs.qld.gov.au says...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.

re: Recursion

Philip Potter wrote:
Da!

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