Recursive thinking problem

[andrew.butt]

Hello, I am a new programmer and am faced with a problem which I am not
totally sure how to start. The problem is as follows:

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

Using recursion, compute the area of a polygone. Cut off a triangle
and use the fact that a triangle with corners (x1,y1), (x2,y2), (x3,
y3) has
area = |(x1)(y2) + (x2)(y2) + (x3)(y1) - (y1)(x2) - (y2x3) - (y3x1)|/2

The program will be testerd by redirecting a text file to its standard
input. Such a file represent a polygone. Within a file, each line
contains two (non-scientific notation) floating point number to
indicate the corrdinates of a vertex.
====================================================

My major problem is that I have not totally developed the recursive
thought that it involves, I can visualize doing this non-recursively
quite easily, so if anyone could offer any advice on how a recursive
approach to this would be started I would be very greatful.

Thanks.

 

[jcsnippets.atspace.com]

Hello, I am a new programmer and am faced with a problem which I am not
totally sure how to start. The problem is as follows:

My major problem is that I have not totally developed the recursive
thought that it involves, I can visualize doing this non-recursively
quite easily, so if anyone could offer any advice on how a recursive
approach to this would be started I would be very greatful.

As always, Google is your friend - these are the first three hits I received
when looking for "recursive programming".

What is recursion?
http://en.wikipedia.org/wiki/Recursion
Mastering recursive programming
http://www-128.ibm.com/developerworks/linux/library/l-recurs.html
Recursion programming
http://personal.vsnl.com/erwin/recursion.htm

Have fun!

JayCee

 

[Chris Uppal]

My major problem is that I have not totally developed the recursive
thought that it involves, I can visualize doing this non-recursively
quite easily, so if anyone could offer any advice on how a recursive
approach to this would be started I would be very greatful.

It might help (if only your confidence ;-) to know that this isn't really a
very natural problem to solve recursively -- i.e. using recursion doesn't gain
you anything in clarity or efficiency over the iterative solution you can
already see.

Anyway, a recursive statement of how to solve it.

To get the area of aShape:
Is aShape triangular ?
If so use the formula and return the result.
Otherwise split it into two sub-Shapes, call 'em A and B.
Use this procedure (recursively) to work out the area of A.
Use this procedure (recursively) to work out the area of B.
Add the two sub-areas together, and return the result.

(I don't want to post code since you've said this is homework).

One interesting thing is that you have almost complete freedom about how you
split the shape into two. You can split it on a line from any vertex to any of
the others (providing they are not actually adjacent). In some recursive
algorithms (for different purposes) choosing where to split the problem up can
make a very important difference to how efficiently it runs -- usually you want
to split the problem into two equally-size sub-problems. Unfortunately that's
not the case here, or it would be a better example.

-- chris

 

[Furious George]

It might help (if only your confidence ;-) to know that this isn't really a
very natural problem to solve recursively -- i.e. using recursion doesn't gain
you anything in clarity or efficiency over the iterative solution you can
already see.

Anyway, a recursive statement of how to solve it.

To get the area of aShape:
Is aShape triangular ?
If so use the formula and return the result.
Otherwise split it into two sub-Shapes, call 'em A and B.
Use this procedure (recursively) to work out the area of A.
Use this procedure (recursively) to work out the area of B.
Add the two sub-areas together, and return the result.

(I don't want to post code since you've said this is homework).

One interesting thing is that you have almost complete freedom about how you
split the shape into two. You can split it on a line from any vertex to any of
the others (providing they are not actually adjacent). In some recursive
algorithms (for different purposes) choosing where to split the problem up can
make a very important difference to how efficiently it runs -- usually you want
to split the problem into two equally-size sub-problems. Unfortunately that's
not the case here, or it would be a better example.

The algorithm appears to assume that the polygons are convex. I
provide a counter-example: a concave pentagon ABCDE where
A=0,0
B=0,100
C=50,100
D=100,100
E=100,0
The area of ABCDE should be 7500, but if BD was used as the splitting
line then the area would be incorrectly computed (using the algorithm)
as 12500.

In order to fix this problem, the algorithm should always choose
splitting line segments that are entirely contained within the polygon.
This reduces the OP's freedom considerably.

 

[Chris Uppal]

The algorithm appears to assume that the polygons are convex.

That's true. I presume that assumption is valid for this exercise. I hope it's
a useful (to the OP) example of recursive thinking anyway.

Another way to generalise the algorithm would be to consider that if you
"split" a polygon by drawing a line outside the shape, then one of the two
sub-shapes you produce has negative area. Details of how you decide which
sub-shape is negative are left as an exercise for the reader[*] ;-)

-- chris

([*] especially as "area" doesn't have an unambiguous definition for
self-intersecting shapes like pentangles)

 

[Dave Mandelin]

I think other posters have given you plenty of information to solve the
problem, but I wanted to kick out a thought about recursion:

Recursion is actually the easy way to do things. But, recursion is
often explained poorly, and explained in a way that makes it seem hard,
so people think it's hard, and it ends up being hard, as a
self-fulfilling prophesy. So, first off, tell yourself that recursion
is actually easy, and don't think hard about it.

The other thing that makes it hard is when you think about it in the
wrong way, and most explanations of recursion emphasize the wrong way.
The right way can be explained in just one sentence: Think of how to
express your problem in terms of a 'smaller' version of itself. That's
all. In your case:

"To compute the area of a polygon, split it into a triangle and the
rest of the polygon (which is a smaller polygon). The area is then the
area of the triangle plus the area of the smaller polygon."

This seems pretty natural and is almost implicit in what you wrote
yourself. The idea is to be 'lazy': instead of solving the problem,
just figure out how to chip off one little piece so the problem is
smaller, and assume somebody else will take care of the rest.

To finish, all you have to do is translate this into code, which you
know how to do, remembering that:

1. You can call the procedure you are writing to solve 'smaller'
problems, such as getting the area of the smaller polygon.

2. At some point, there will be a base, which is easy enough to solve
directly, even for a 'lazy' programmer. For your problem, it's the area
of a 2-gon (a line), which is 0. (It would also work to use the area of
a triangle as a base, but as I try to be as lazy as possible, I prefer
picking a base where the answer is just 0.)


Another thing that you may find useful is that there is a 'standard'
translation from any single loop iterative implementation into a
recursive implementation. I imagine that your non-recursive solution
goes over a loop n-2 times, adding up areas. The recursive version is
based on this statement:

"The value after k iterations is equal to the value after k-1
iterations plus the amount computed inside the kth iteration."

You can transform any 'simple' loop into a recursive procedure this
way. Sometimes you can also see a simple definition of what the
recursive procedure does after this. In this case, it turns out to be
"compute the area of a polygon formed of k triangles".

Anyway, let me know if this helps at all, or if it doesn't help at all.
I would like to know if it's a better way of explaining recursion.

Dave

 

[Andrew]

Thank you all very much for your help
And indeed your assumption that this is for convex only is true
Thanks.
-Andrew