Just another Perl shrine 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?

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.

Create A New User
Node Status?
node history
Node Type: note [id://715797]
help
Chatterbox?
and all is quiet...

How do I use this? | Other CB clients
Other Users?
Others chanting in the Monastery: (5)
As of 2018-05-28 06:28 GMT
Sections?
Information?
Find Nodes?
Leftovers?
Voting Booth?
World peace can best be achieved by:

Results (199 votes). Check out past polls.

Notices?