Beefy Boxes and Bandwidth Generously Provided by pair Networks
Perl-Sensitive Sunglasses
 
PerlMonks  

Re: Fibonacci golf with one state variable

by dragonchild (Archbishop)
on Oct 07, 2008 at 14:25 UTC ( #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?


Comment on Re: Fibonacci golf with one state variable
Download Code
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
Node Status?
node history
Node Type: note [id://715797]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others contemplating the Monastery: (10)
As of 2015-07-31 18:57 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    The top three priorities of my open tasks are (in descending order of likelihood to be worked on) ...









    Results (280 votes), past polls