Velocity Reviews > Java > Recursion Program finding root of equation

# Recursion Program finding root of equation

michalik.ireneusz@gmail.com
Guest
Posts: n/a

 10-22-2008
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

Patricia Shanahan
Guest
Posts: n/a

 10-22-2008
http://www.velocityreviews.com/forums/(E-Mail Removed) 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
Guest
Posts: n/a

 10-22-2008
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

Martin Gregorie
Guest
Posts: n/a

 10-22-2008
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 |

Daniel Pitts
Guest
Posts: n/a

 10-22-2008
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/>

Martin Gregorie
Guest
Posts: n/a

 10-22-2008
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 |

Mark Space
Guest
Posts: n/a

 10-23-2008
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.

Martin Gregorie
Guest
Posts: n/a

 10-23-2008
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 |

Andreas Leitgeb
Guest
Posts: n/a

 10-23-2008
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...S/Recn/Binary/

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

Harold Yarmouth
Guest
Posts: n/a

 10-23-2008
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...S/Recn/Binary/
>
> (search down for fastest)

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