Recursing code problem

[snowdy]

I am using Interactive C with my handboard (68HC11) development system but
I've got a problem that I am asking for help with.
I am not new to C but learning all the time and I just cant see how to
overcome this problem.

Symptom:
Programs fail ' Runtime error' which equates to a stack error.
This is because my code is like going around and around (a snake chasing its
tail is a term I've seen used) but I cant quite come to grips with how to
overcome this problem.

Should I post some of the code up on this group for people with a better
knowledge of this problem to make suggestions - I feel its probably
something not difficult to understand but I just need a little guidance
here.

Jeff

 

[Artie Gold]

I am using Interactive C with my handboard (68HC11) development system but
I've got a problem that I am asking for help with.
I am not new to C but learning all the time and I just cant see how to
overcome this problem.

Symptom:
Programs fail ' Runtime error' which equates to a stack error.
This is because my code is like going around and around (a snake chasing its
tail is a term I've seen used) but I cant quite come to grips with how to
overcome this problem.

Should I post some of the code up on this group for people with a better
knowledge of this problem to make suggestions - I feel its probably
something not difficult to understand but I just need a little guidance
here.

Post the smallest compilable snippet that exhibits the problem you're
having.

HTH,
--ag

 

[Julian V. Noble]

I am using Interactive C with my handboard (68HC11) development system but
I've got a problem that I am asking for help with.
I am not new to C but learning all the time and I just cant see how to
overcome this problem.

Symptom:
Programs fail ' Runtime error' which equates to a stack error.
This is because my code is like going around and around (a snake chasing its
tail is a term I've seen used) but I cant quite come to grips with how to
overcome this problem.

Should I post some of the code up on this group for people with a better
knowledge of this problem to make suggestions - I feel its probably
something not difficult to understand but I just need a little guidance
here.

Jeff

Post some code. However, your symptoms sound like you don't
have a proper termination condition. One problem with recursive
code (and I use it a lot and even wrote a column about it) is that
it is easy to create an endless loop that overwrites the stack.

Also, some problems are not well-suited to recursion: the stack
gets too deep and boom! So you ought to analyze your code to
estimate how the stack-depth grows with problem size.

You can find my column, Recurses!, at

http://www.phys.virginia.edu/classes/551.jvn.fall01/CiSE_progs/Cprogs.htm

--
Julian V. Noble
Professor Emeritus of Physics
(e-mail address removed)
^^^^^^^^^^^^^^^^^^
http://galileo.phys.virginia.edu/~jvn/

"Science knows only one commandment: contribute to science."
-- Bertolt Brecht, "Galileo".

 

[ArWeGod]

....snip...

Symptom:
Programs fail ' Runtime error' which equates to a stack error.
This is because my code is like going around and around (a snake chasing its
tail is a term I've seen used) but I cant quite come to grips with how to
overcome this problem.
....snip...
Jeff

I've also run into this problem. Here's something simple to try:
==============================
/*
factorial.c
Takes one command-line argument: the number you want the factorial of.
Breaks at around 39! with the following:
run-time error R6000
- stack overflow
*/

#include <stdio.h>
#include <stdlib.h>

double fact (int n);

void main(int argc, char **argv)
{
int n;
double factorial=1;

n = atoi (argv[1]);
fact (n);
}

double fact (int n)
{
static double value=1;

if (n > 1)
value = n * fact (n-1);

printf ("%3.d! = %.0f \n", n, value);

return (value);
}

==============================

So, I have the same question. How can I increase the stack or otherwise make
this work for higher numbers?

 

[Malcolm]

/*
factorial.c
Takes one command-line argument: the number you want the factorial > of.
Breaks at around 39! with the following:
run-time error R6000
- stack overflow
*/


double fact (int n)
{
static double value=1;

if (n > 1)
value = n * fact (n-1);

printf ("%3.d! = %.0f \n", n, value);

return (value);
}

So, I have the same question. How can I increase the stack or
otherwise make this work for higher numbers?

This surprises me, because even a relatively puny stack shouldn't overflow
at a depth of 39 functions.
What will overflow quite rapidly is the precision of a double.

 

[Neil Cerutti]

<rant topicality="zero">
Why do people so often talk about factorials or the Fibonacci
numbers when explaining recursion? Neither is well- suited to
a recursive solution; iteration wins on practically every
measure. And for the Fibonacci numbers, iteration itself is
easily beatable; recursion is at best a poor third choice. But
look up any textbook or lecture about recursion, and what do
you find? Factorials and Fibonacci! Foolishness!

</rant>

Because factorials and fibonacci number's make such wonderfully
simple recursive functions. The crappyness of the resulting
solutions isn't a consideration when the intent is to educate.

A program that is "best" written recursively, like a program that
shows all the possible ways to make a certain amount of change,
may be too complicated for an introduction to recursion.

<rant> I think the word "recursion" should be abolished from
primmers. It just creates consternation. I could create a similar
effect by constantly using the word "ambulation" to describe the
act of going for a walk. </rant>

 

[Alan Balmer]

Why do people so often talk about factorials or the
Fibonacci numbers when explaining recursion?

For the same reason they talk about the bubble sort when introducing
sorting - it's easily understood.

 

[Glen Herrmannsfeldt]

(snip regarding recursive functions)

<rant> I think the word "recursion" should be abolished from
primmers. It just creates consternation. I could create a similar
effect by constantly using the word "ambulation" to describe the
act of going for a walk. </rant>

How about reentrant, which isn't quite the same, but related.

Along the same line, there is refreshable and serially reusable.

-- glen

 

[ArWeGod]

This surprises me, because even a relatively puny stack shouldn't overflow
at a depth of 39 functions.
What will overflow quite rapidly is the precision of a double.

You may have hit the nail on the head.
The value I get for 38! is 523022617466601000000000000000000000000000000.

Q1. Anybody know the limit of a double?

Q2. Anybody know of a bigger number - holder? long double? unsigned double?
etc.

I guess for this sort of thing you need to do your number handling for
overflow, etc.

 

[Alan Balmer]

You may have hit the nail on the head.
The value I get for 38! is 523022617466601000000000000000000000000000000.

That won't cause a stack overflow.

Q1. Anybody know the limit of a double? Implementation dependent.

Q2. Anybody know of a bigger number - holder? long double? unsigned double?
etc.

Google for "big number" packages.


BTW, I just read your classification of programmers from newby to 5+
years. Apparently that was from observation, not practice?

 

[Ben Pfaff]

Q1. Anybody know the limit of a double?

DBL_MAX

 

[ArWeGod]

DBL_MAX

So, is

#define DBL_MAX 1.7976931348623158e+308 /* max value */ // my MSVC
compiler's value

more than

523022617466601000000000000000000000000000000 * 39?

....I _think_ I get an overflow error. If not it's a recursion problem. You
tell me. I'm NOT going to do the math - I have a few critics - you work it
out!

But, please, don't attack me, just post the correct answer to help
everybody. I don't really care - I've never calculated factorials, I just
wrote the program because it was asked it on a job interview and I was
checking my work.

;-)

 

[Ben Pfaff]

So, is

#define DBL_MAX 1.7976931348623158e+308 /* max value */ // my MSVC
compiler's value

more than

523022617466601000000000000000000000000000000 * 39?

Yes. Written out in full, 1.7976931348623158e+308 is
179769313486231580000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000,
more than a googol times larger than
523022617466601000000000000000000000000000000 * 39.

I don't know what your exact problem is, not having examined the
situation closely. Floating-point calculations are notoriously
tricky. But the problem should not be one of overflow.

 

[pete]

Factorials and Fibonacci are dealt only in beginner/intermediate
level books. That is because, it is easier to convey the recursive
logic via these simple Factorials and Fibonacci.

Professor has mentioned his recursive programs of
http://www.phys.virginia.edu/classes/551.jvn.fall01/CiSE_progs/Cprogs.htm
But, most of the programs that he mentioned won't be suited to explain
the recursive logic in simple beginners' book.

The 8 queens problem seems to be a good one to me for recursion,
but that's the only one that I know.

 

[Julian V. Noble]

I've also run into this problem. Here's something simple to try:
[... recursive computation of factorial snipped ...]

So, I have the same question. How can I increase the stack or otherwise make
this work for higher numbers?

It is possible to express any recursive computation in
iterative form, but that doesn't mean iteration is always
the best technique to use. It is possible to express any
iterative computation in recursive form, but that doesn't
mean recursion is always the best technique to use.

If you need to compute factorials (an iffy business
at best, by the way), iteration is a better approach than
recursion.

<rant topicality="zero">

Why do people so often talk about factorials or the
Fibonacci numbers when explaining recursion? Neither is well-
suited to a recursive solution; iteration wins on practically
every measure. And for the Fibonacci numbers, iteration itself
is easily beatable; recursion is at best a poor third choice.
But look up any textbook or lecture about recursion, and what
do you find? Factorials and Fibonacci! Foolishness!

</rant>

Quite right. In my column "Recurses!" I said essentially the same thing.
Another frequently used example that is almost as bad is string
reversal. Here is an example in M$ QuickBASIC:

FUNCTION rev$ (a$)
c$ = MID$(a$, 1, 1)
IF c$ = "" THEN
rev$ = ""
ELSE
rev$ = rev$(MID$(a$, 2)) + c$
END IF
END FUNCTION

I am sure there must be C versions floating around but I haven't
time to look for one or to translate the above. Someday...


--
Julian V. Noble
Professor Emeritus of Physics
(e-mail address removed)
^^^^^^^^^^^^^^^^^^
http://galileo.phys.virginia.edu/~jvn/

"Science knows only one commandment: contribute to science."
-- Bertolt Brecht, "Galileo".

 

[Joona I Palaste]

Quite right. In my column "Recurses!" I said essentially the same thing.
Another frequently used example that is almost as bad is string
reversal. Here is an example in M$ QuickBASIC:

FUNCTION rev$ (a$)
c$ = MID$(a$, 1, 1)

This would be more readable as:
c$ = LEFT$(a$, 1)

IF c$ = "" THEN
rev$ = ""
ELSE
rev$ = rev$(MID$(a$, 2)) + c$
END IF
END FUNCTION

--
/-- Joona Palaste ([email protected]) ---------------------------\
| Kingpriest of "The Flying Lemon Tree" G++ FR FW+ M- #108 D+ ADA N+++|
| http://www.helsinki.fi/~palaste W++ B OP+ |
\----------------------------------------- Finland rules! ------------/
"C++. C++ run. Run, ++, run."
- JIPsoft

 

[Arthur J. O'Dwyer]

While we're here, a joke...

"Knock, Knock"
"Who's there?"
"Recursion."
"Recursion who?"

"Knock, Knock"
...

No, no, no! ;-)

"Knock, knock."
"Who's there?"
"Iteration."
"Iteration who?"
"Knock knock."
"Who's there?"
"Iteration."
"Iteration who?"
"Knock knock."
"Who's there?"
"Orange."
"Orange who?..."


"Knock knock."
"Who's there?"
"Recursion."
"Recursion who?"
"Recursion knock knock."
"Recursion knock knock who?"
"Recursion knock knock knock."
"Who's there?..."

-Arthur

 

[Paul Hsieh]

<rant topicality="zero">

Why do people so often talk about factorials or the
Fibonacci numbers when explaining recursion? Neither is well-
suited to a recursive solution; iteration wins on practically
every measure.

Not necessarily so. The following is a re-expression of the fibonacci
sequence recursive formula:

f[0] = 0
f[1] = 1
f[2] = 1
f[n] = f[(n+1)/2]^2 + f[(n-1)/2]^2 ; if n is odd
= f[n/2+1]^2 - f[n/2-1]^2 ; if n is even

Which implies a recursion of depth about ln(n) steps. Now if you do
the math, you will realize that the total number of calls does in fact
lead to O(n) which might lead you to believe that iterative is faster
(since its less complicated). However, if you cache the values as you
compute them, then this should run in about O((ln(n))^2) which should
*SKUNK* the iterative solution for large enough n.

[...] And for the Fibonacci numbers, iteration itself
is easily beatable;

By a complete table look up of course! (No this will not blow out your
memory; think about it.)

[...] recursion is at best a poor third choice.

As I pointed out above, depends on which recursive formula you are
talking about.

But look up any textbook or lecture about recursion, and what
do you find? Factorials and Fibonacci! Foolishness!

They are the easiest examples -- they can't explain trees until they
explain recursion.

 

[Martin Dickopp]

By a complete table look up of course!

One easy way to calculate the `n'-th Fibonacci number `f' without a table
is this:

const double sqrt5 = sqrt (5.0);
const double golden = 0.5 + 0.5 * sqrt5;

int f = (int)(pow (golden, (double)n) / sqrt5 + 0.5);

Martin

 

[Kevin D. Quitt]

The value I get for 38! is 523022617466601000000000000000000000000000000.

The correct value is 523022617466601111760007224100074291200000000

You aren't suffering from overflow, but from a loss of precision because a
double doesn't hold enough bits to represent the correct value.

(And 39! is 20397882081197443358640281739902897356800000000)

169! (~4.3e305) is the largest value a double can hold without overflow:

42690680090047052749392518888995665380688186360567
36103849163411117977554942180092854323970142716152
65381823013990501222156824856790750177960523574894
55946484708413412107621199803603527401512378815048
78975040568419670360154453585262827477179746400268
93725894862438400000000000000000000000000000000000
00000