# Recursion Program finding root of equation

Discussion in 'Java' started by michalik.ireneusz@gmail.com, Oct 22, 2008.

1. ### Guest

I need help writing a program when given two variables, a high and a
low, and given an equation, that will find the zero of the equation
based on using the sign change on either side of the zero, if you
could help me out it would be greatly appreciated

, Oct 22, 2008

2. ### Patricia ShanahanGuest

wrote:
> I need help writing a program when given two variables, a high and a
> low, and given an equation, that will find the zero of the equation
> based on using the sign change on either side of the zero, if you
> could help me out it would be greatly appreciated

Note that you cannot count on there being a zero unless the function is
continuous.

Can you describe what sort of help you need? Do you understand the
objective, and the underlying mathematical idea? Do you understand
recursion?

Assuming you understand both recursion and the objective, you should
begin by doing the task with pencil and paper for some very simple function.

Patricia

Patricia Shanahan, Oct 22, 2008

3. ### Patricia ShanahanGuest

Eric Sosman wrote:
....
> I'm not sure why you're interested in a recursive framework,
> though. ...

I think this may relate to one of the more difficult problems in
computer science education - finding good example problems for teaching
recursion and making sure students have understood it.

Patricia

Patricia Shanahan, Oct 22, 2008
4. ### Martin GregorieGuest

Re: [OT] Re: Recursion Program finding root of equation

On Wed, 22 Oct 2008 14:36:00 -0400, Eric Sosman wrote:

> Could be. At least the teacher has not dragged out the Fibonacci
> numbers, which are a *terrible* use of recursion but are for some reason
> *always* used to illustrate it ...
>

I've always liked code to create and walk a binary tree to illustrate
recursion.

--
martin@ | Martin Gregorie
gregorie. | Essex, UK
org |

Martin Gregorie, Oct 22, 2008
5. ### Daniel PittsGuest

Re: [OT] Re: Recursion Program finding root of equation

Martin Gregorie wrote:
> On Wed, 22 Oct 2008 14:36:00 -0400, Eric Sosman wrote:
>
>> Could be. At least the teacher has not dragged out the Fibonacci
>> numbers, which are a *terrible* use of recursion but are for some reason
>> *always* used to illustrate it ...
>>

> I've always liked code to create and walk a binary tree to illustrate
> recursion.
>
>

Walk, sure. Create, no.

--
Daniel Pitts' Tech Blog: <http://virtualinfinity.net/wordpress/>

Daniel Pitts, Oct 22, 2008
6. ### Martin GregorieGuest

Re: [OT] Re: Recursion Program finding root of equation

On Wed, 22 Oct 2008 14:09:13 -0700, Daniel Pitts wrote:

> Martin Gregorie wrote:
>> On Wed, 22 Oct 2008 14:36:00 -0400, Eric Sosman wrote:
>>
>>> Could be. At least the teacher has not dragged out the Fibonacci
>>> numbers, which are a *terrible* use of recursion but are for some
>>> reason *always* used to illustrate it ...
>>>

>> I've always liked code to create and walk a binary tree to illustrate
>> recursion.
>>
>>

> Walk, sure. Create, no.

I should clarify here that I mean a plain (non-balanced) binary tree with
a single key value in every node. You walk the tree to find the insertion
point, slap your new node in to replace the existing left or right link
and attach the rest of that branch to it.

Of course you can't remove a node from such a tree or (usually) change
the key value in a node, but its plenty good enough for a small to medium
one-time tree that will be grown, walked and scrapped. Yes, it may be
slow if its gets very degenerate, but OTOH its fast to build and to
traverse.

--
martin@ | Martin Gregorie
gregorie. | Essex, UK
org |

Martin Gregorie, Oct 23, 2008
7. ### Mark SpaceGuest

Re: [OT] Re: Recursion Program finding root of equation

Martin Gregorie wrote:

> I should clarify here that I mean a plain (non-balanced) binary tree with
> a single key value in every node. You walk the tree to find the insertion

I think recursive walks are bad too. Most moder CPUs have a relatively
small cache with will negatively impact performance if they are written
to gratuitously. This include stack, which is cached locally too.

Recursive algorithms tend to eat up stack space quickly, and will thrash
the local cache. AMD recommends that no recursive algorithms be employ
on its CPUs as the performance hit is too great. I can't find that
quote right now, but I'm sure that's accurate.

Mark Space, Oct 23, 2008
8. ### Martin GregorieGuest

Re: [OT] Re: Recursion Program finding root of equation

On Wed, 22 Oct 2008 20:05:36 -0700, Mark Space wrote:

> I think recursive walks are bad too.
>

I won't argue with that.

Just remember we've been talking about recursion examples for teaching

When I had to implement a fast, in-memory lookup of a non-static tree I
used the red-black balanced tree algorithm in Sedgwick's "Algorithms".
This is iterative, not recursive and inserts aren't particularly
expensive.

The tree was, err, quite large - last time I saw it there were 3 million
nodes and growing. The process was running at around 20,000 lookups a
second on an Alphaserver EV6 cpu in case you're interested. The main
reason for the speed was that the maximum search depth was about 23 since
the tree was balanced.

--
martin@ | Martin Gregorie
gregorie. | Essex, UK
org |

Martin Gregorie, Oct 23, 2008
9. ### Andreas LeitgebGuest

Re: [OT] Re: Recursion Program finding root of equation

bugbear <bugbear@trim_papermule.co.uk_trim> wrote:
> Here's a recursive version of fib that will beat the usual iterative
> version out of sight:
> http://www.csse.monash.edu.au/~lloyd/tildeAlgDS/Recn/Binary/

cool. Thanks for the link.

Btw, there is also a (theoretically) constant time
algorithm: namely the closed formula, which involves
a sum of each n-powered golden-cut and one-minus-
golden-cut, iirc. It requires a hell of an exact
floating point library, though

Andreas Leitgeb, Oct 23, 2008
10. ### Harold YarmouthGuest

Re: [OT] Re: Recursion Program finding root of equation

bugbear wrote:
> Here's a recursive version of fib that will beat the usual iterative
> version out of sight:
>
> http://www.csse.monash.edu.au/~lloyd/tildeAlgDS/Recn/Binary/
>
> (search down for fastest)

That, of course, has an iterative version of its own.

Harold Yarmouth, Oct 23, 2008
11. ### Harold YarmouthGuest

Re: [OT] Re: Recursion Program finding root of equation

bugbear wrote:
> Harold Yarmouth wrote:
>> bugbear wrote:
>>> Here's a recursive version of fib that will beat the usual iterative
>>> version out of sight:
>>>
>>> http://www.csse.monash.edu.au/~lloyd/tildeAlgDS/Recn/Binary/
>>>
>>> (search down for fastest)

>>
>> That, of course, has an iterative version of its own.

>
> Of course; converting between recursive and iterative
> implementations of the same basic algorithms
> is a common comp-sci exercise.
>
> I was careful to say "usual iterative version".

My point is that there is an iterative version that seems to beat all
recursive versions, even if it is NOT the "usual" iterative version.

(I expect an iterative version with no explicit stack to beat a
recursive version that's otherwise essentially the same, except for a
tail-recursive version on a system like lisp that aggressively optimizes
those. Which I understand they do by turning them into iterations, by
the by.)

Harold Yarmouth, Oct 23, 2008
12. ### Guest

On Oct 23, 10:07 am, Harold Yarmouth <>
wrote:
> bugbear wrote:
> > Harold Yarmouth wrote:
> >> bugbear wrote:
> >>> Here's a recursive version of fib that will beat the usual iterative
> >>> version out of sight:

>
>
> >>> (search down for fastest)

>
> >> That, of course, has an iterative version of its own.

>
> > Of course; converting between recursive and iterative
> > implementations of the same basic algorithms
> > is a common comp-sci exercise.

>
> > I was careful to say "usual iterative version".

>
> My point is that there is an iterative version that seems to beat all
> recursive versions, even if it is NOT the "usual" iterative version.
>
> (I expect an iterative version with no explicit stack to beat a
> recursive version that's otherwise essentially the same, except for a
> tail-recursive version on a system like lisp that aggressively optimizes
> those. Which I understand they do by turning them into iterations, by
> the by.)- Hide quoted text -
>
> - Show quoted text -

Would anyone know how to write this program?????

, Oct 23, 2008
13. ### Andreas LeitgebGuest

Re: [OT] Re: Recursion Program finding root of equation

Tim Smith <> wrote:
>> Btw, there is also a (theoretically) constant time
>> algorithm: namely the closed formula, ...

> The normal Java double is good enough to go out to F70:

The way you did it, it's not really constant time.

I meant: do the exponentiation as exp(log(phi)*n)
and see up to which n this will work out precise
when rounded to long.

I didn't try it myself, so maybe it's even more
precise than repeated multiplication, afterall

Andreas Leitgeb, Oct 23, 2008
14. ### Patricia ShanahanGuest

Re: [OT] Re: Recursion Program finding root of equation

Andreas Leitgeb wrote:
> Tim Smith <> wrote:
>>> Btw, there is also a (theoretically) constant time
>>> algorithm: namely the closed formula, ...

>> The normal Java double is good enough to go out to F70:

>
> The way you did it, it's not really constant time.
>
> I meant: do the exponentiation as exp(log(phi)*n)
> and see up to which n this will work out precise
> when rounded to long.

Why "exp(log(phi))*n)" rather than Math.pow(phi,n)?

I tested the closed form method using Math.pow and it is exact through n=70.

Patricia

Patricia Shanahan, Oct 23, 2008
15. ### Andreas LeitgebGuest

Re: [OT] Re: Recursion Program finding root of equation

Patricia Shanahan <> wrote:
> Andreas Leitgeb wrote:
>> Tim Smith <> wrote:
>>>> Btw, there is also a (theoretically) constant time
>>>> algorithm: namely the closed formula, ...
>>> The normal Java double is good enough to go out to F70:

>>
>> The way you did it, it's not really constant time.
>>
>> I meant: do the exponentiation as exp(log(phi)*n)
>> and see up to which n this will work out precise
>> when rounded to long.

> Why "exp(log(phi))*n)" rather than Math.pow(phi,n)?
> I tested the closed form method using Math.pow and it is exact through n=70.

I don't know Math.pow()'s implementation. With integer exponents
it may just do some clever repeated multiplication and squaring
based on binary representation of "n". Maybe it does, then it's
not a O(1) but O(log n)). Or it does not, then it more or less *is*
just exp(log(phi)*n), anyway (except for corner cases not relevant
to phi and n).

Math.pow() takes two doubles, but it's javadoc does mention
cases where the exponent may be an odd or even integer,
so any integer-based "optimisations" are not infeasible.

Iow, Math.pow() might possibly maximize precision at cost
of performance, which often is just fine, but destroys the
O(1)-claim. That this O(1)-claim is actually bogus, anyway,
is a different story and beyond the fields of my/our theorizing

Andreas Leitgeb, Oct 23, 2008
16. ### Roedy GreenGuest

On Wed, 22 Oct 2008 09:36:24 -0700 (PDT),
wrote, quoted or indirectly quoted someone who said :

>I need help writing a program when given two variables, a high and a
>low, and given an equation, that will find the zero of the equation
>based on using the sign change on either side of the zero, if you
>could help me out it would be greatly appreciated

You don't typically solve such a problem with recursion, unless you
are a mathematician. You use iteration (a loop) then terminates after
so much time or once the answer gets close enough.

This is the subject of a year's course in numerical analysis at
university. You might check your local university to see what text
book they recommend for the numerical analysis course.

If your equation is well behaved without multiple roots,
discontinuities etc, you can use Newton Raphson. Google.

You can do an even simpler version with a binary search.
--
Roedy Green Canadian Mind Products
http://mindprod.com
A vote for McCain is fearful clinging to McSame.
A vote for Obama is a shot at Obamalot.

Roedy Green, Oct 30, 2008