Recursion

[MakeMineScotch]

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

 

[Sjouke Burry]

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]

MakeMineScotch wrote:

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!

 

[Jim Langston]

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.

 

[=?ISO-8859-1?Q?=22Nils_O=2E_Sel=E5sdal=22?=]

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]

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

 

[Jim Langston]

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]

The recursions that are not just clever loops, they are stack algorithms,
with a FIFO situation.

ITYM LIFO...

Philip

 

[Jerry Coffin]

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

 

[Phlip]

ITYM LIFO...

Da!