Beefy Boxes and Bandwidth Generously Provided by pair Networks
Just another Perl shrine
 
PerlMonks  

Re: Fibonacci golf with one state variable

by dragonchild (Archbishop)
on Oct 07, 2008 at 14:25 UTC ( [id://715797]=note: print w/replies, xml ) Need Help??


in reply to Fibonacci golf with one state variable

How about a tail-recursive version with no state variables?
perl -E 'sub f{say$_[0];goto&f($_[1],$_[0]+$_[1])}f(1,1)'
And I'm sure that could be reduced further. And, no, the stack doesn't count as a state variable. :-p

My criteria for good software:
  1. Does it work?
  2. Can someone else come in, make a change, and be reasonably certain no bugs were introduced?

Replies are listed 'Best First'.
Re^2: Fibonacci golf with one state variable
by aufflick (Deacon) on Oct 08, 2008 at 02:05 UTC

    Sure, of course...

    I'm wondering, though, why the goto&f? It works perfectly well as:

    perl -E 'sub f{say$_[0];f($_[1],$_[0]+$_[1])}f(1,1)' |head -10

    If you want to use the & form that saves on stack operations by not creating a new @_, you could do this (paying careful attention to the right to left execution):

    perl -E 'sub f{say$_[0];$_[1]=$_[1]+shift;&f}f(1,1)' |head -10

    Which is exactly the same length, but less operations. Now if only Perl auto-optimised tail recursion...

    It's a shame that unshift doesn't default to @_ like shift otherwise I could save one character by switching the order of the values on the stack:

    perl -E 'sub f{say$_[1];unshift@_,$_[0]+pop;&f}f(1,1)' |head -10

    Update: I just read the perldoc for goto and I have to say I didn't know that goto &NAME form, so thanks for the learning exercise!. Like my form it won't result in recursive stack blowout. Without studying the internals too carefully I don't know which would result in less operations. Maybe a benchmark will show.

Log In?
Username:
Password:

What's my password?
Create A New User
Domain Nodelet?
Node Status?
node history
Node Type: note [id://715797]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this?Last hourOther CB clients
Other Users?
Others cooling their heels in the Monastery: (5)
As of 2024-04-25 08:51 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    No recent polls found