Velocity Reviews > Recursing code problem

Recursing code problem

Ben Pfaff
Guest
Posts: n/a

 08-30-2003
"ArWeGod" <(E-Mail Removed)> writes:

> Q1. Anybody know the limit of a double?

DBL_MAX
--
A competent C programmer knows how to write C programs correctly,
a C expert knows enough to argue with Dan Pop, and a C expert
expert knows not to bother.

ArWeGod
Guest
Posts: n/a

 08-30-2003
"Ben Pfaff" <(E-Mail Removed)> wrote in message
news:(E-Mail Removed)...
> "ArWeGod" <(E-Mail Removed)> writes:
>
> > Q1. Anybody know the limit of a double?

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

--
ArWeGod

Ben Pfaff
Guest
Posts: n/a

 08-30-2003
"ArWeGod" <(E-Mail Removed)> writes:

> "Ben Pfaff" <(E-Mail Removed)> wrote in message
> news:(E-Mail Removed)...
> > "ArWeGod" <(E-Mail Removed)> writes:
> >
> > > Q1. Anybody know the limit of a double?

> >
> > DBL_MAX

>
> 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
17976931348623158000000000000000000000000000000000 00000000000000000000000000000000000000000000000000 00000000000000000000000000000000000000000000000000 00000000000000000000000000000000000000000000000000 00000000000000000000000000000000000000000000000000 00000000000000000000000000000000000000000000000000 000000000,
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.

--
"I hope, some day, to learn to read.
It seems to be even harder than writing."
--Richard Heathfield

pete
Guest
Posts: n/a

 08-30-2003
R. Rajesh Jeba Anbiah wrote:
>
> Eric Sosman <(E-Mail Removed)> wrote in message news:<(E-Mail Removed)>...
> > 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!

>
> 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...ogs/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.

--
pete

Julian V. Noble
Guest
Posts: n/a

 08-30-2003
Eric Sosman wrote:
>
> ArWeGod wrote:
> >
> > 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
http://www.velocityreviews.com/forums/(E-Mail Removed)
^^^^^^^^^^^^^^^^^^
http://galileo.phys.virginia.edu/~jvn/

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

Joona I Palaste
Guest
Posts: n/a

 08-31-2003
Julian V. Noble <(E-Mail Removed)> scribbled the following:
> 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 ((E-Mail Removed)) ---------------------------\
| 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
Guest
Posts: n/a

 08-31-2003

On Sat, 30 Aug 2003, Randy Howard wrote:
>
> In article <(E-Mail Removed)>, (E-Mail Removed) says...
> > <rant topicality="zero">

>
> 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
Guest
Posts: n/a

 08-31-2003
Eric Sosman <(E-Mail Removed)> wrote:
> <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

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

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

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

--
Paul Hsieh
http://www.pobox.com/~qed/
http://bstring.sf.net/

Martin Dickopp
Guest
Posts: n/a

 08-31-2003
(E-Mail Removed) (Paul Hsieh) writes:

> Eric Sosman <(E-Mail Removed)> wrote:
>
> > And for the Fibonacci numbers, iteration itself is easily beatable;

>
> 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
Guest
Posts: n/a

 09-02-2003
On Fri, 29 Aug 2003 22:43:33 GMT, "ArWeGod" <(E-Mail Removed)> wrote:
>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

--
#include <standard.disclaimer>
_
Kevin D Quitt USA 91387-4454 96.37% of all statistics are made up
Per the FCA, this address may not be added to any commercial mail list