recursive pattern

[Keshan Pillay]

Hey I hope everyone is having a good evening/day so far. I was wondering if anyone could please point me in the right direction as to how I could write a function for this?



Many thanks,
as usual, I would appreciate it is someone could explain/help me get to the right answer rather than just giving it to me.

[Keshan Pillay]

Sorry this is the pic I meant to post in last one:

[Norm Radder]

I guess you'll have to enter the problem in words. No picture there to see.

[Ulf Dittmer]

I can see it fine.

[Rob Spoor]

In pseudo code:

public void drawLine(int order, int length)
{
    if (order <= 0) // to also catch negative orders    :wink:   
    {
        drawSimpleLine(length);
        return;
    }
    length = length / 3;
    order = order - 1;
    drawLine(order, length);
    rotate(-60);
    drawLine(order, length);
    rotate(120);
    drawLine(order, length);
    rotate(-60);
    drawLine(order, length);
}

This is basically a translation from words to pseudo code. Now all that you will need to do is implement drawSimpleLine and rotate.

Considering you will be using Swing for this, you can do the drawing with a JPanel:

class MyPanel extends JPanel
{
    protected void paintComponent(Graphics g)
    {
        super.paintComponent(g);
        // do your own drawing here
    }
}

Graphics.drawLine will be your friend here.

One more hint: the Graphics object is usually an instance of Graphics2D. This class has methods to translate and rotate it which may be able to help you.

[ September 28, 2008: Message edited by: Rob Prime ]

Some more hints, after I've implemented this:
1) make the length parameter a double. Otherwise the rounding down will cause the figure to shrink horizontally.
2) don't go higher than order 6; on my machine, order 7 takes between half a second and a full second to paint. Order 8 takes around 4 seconds, 9 goes to 13+ seconds and 10 takes over a minute.
[ September 28, 2008: Message edited by: Rob Prime ]

[Keshan Pillay]

Thanks for your reply Rob, It really helped me out, and I've got it sorted. ^^

[Gamini Sirisena]

This problem fits a recursive solution nicely.

What do you think of using recursion in real life programs for naturally recursive problems? I mean from a performance perspective. Stack overflows etc?

[Campbell Ritchie]

It's not stack overflow quite as much as the risk of getting quadratic or exponential complexity in some instances. You need to be careful about the design; as long as you keep within reasonable bounds of size you only get stack overflow if you have an infinite recursion; whenever I have tried to get the stack size when it overflows it tends to be about 5000, so you oughtn't to get an overflow in most real-life situations.

Consider the usual Fibonacci algorithm which is exponential, but you can write algorithms quite simply which run in linear time, and there is a logarithmic time Fibonacci algorithm too. It is in Kaldewaij, A., Programming: the derivation of algorithms, Prentice Hall International series in computer series, Prentice Hall International, 1990. ISBN 0132041081 250 pages, I think page 98-99.

[Rob Spoor]

Originally posted by Campbell Ritchie:
It is in Kaldewaij, A., Programming: the derivation of algorithms, Prentice Hall International series in computer series, Prentice Hall International, 1990. ISBN 0132041081 250 pages, I think page 98-99.

Great book by the way, it's what we started with in University.

[Ulf Dittmer]

There's nothing wrong with recursion per se. Avoiding it no matter what seems like a premature optimization, which needs to be set against the fact that using a comparable iterative version also has a certain overhead in bookkeeping.

Recursion's perception also suffers from there being bad examples for it out there. Fibonacci numbers are a particularly egregious example, since it leads to tree recursion -which is much worse than linear recursion-, while a simple iterative solution is available.

Recursion depth (and the stack problems if it's too deep) is a real concern, but what's possible depends so much individual circumstances that dismissing recursion out of hand seems a bad idea.

Just my 2 cents.

Update: Pretty similar to Campbell's 2 cents, I see now :-)
[ September 29, 2008: Message edited by: Ulf Dittmer ]

[Campbell Ritchie]

Originally posted by Ulf Dittmer:
Pretty similar to Campbell's 2 cents, I see now :-)

Campbell's 2 pence, please.

[Ulf Dittmer]

Originally posted by Campbell Ritchie:
Campbell's 2 pence, please.

Which these days are better than 2 cents worth of opinion, I take it.

[Campbell Ritchie]

Not if they're eurocents . . .

[Rob Spoor]

Even then.

Pence > euro cents > dollar cents

Unfortunately for me, because I like to buy stuff online in the UK regularly. It would be sooo much better for me if the Pound became less valuable than the Euro
As it is, 1 Euro is still somewhere between 0.70 and 0.80 Pounds.

[Campbell Ritchie]

Originally posted by Rob Prime:
1 Euro is still somewhere between 0.70 and 0.80 Pounds.

Last time I went to Holland 1� was worth �0.64.

[Rob Spoor]

The Euro is worth a bit more now; according to XE.com 1 Euro is now 0.80 Pounds.

But enough of this currency talk now! Back to recursion!