Chad Perrin: SOB

15 December 2006

UCBLogo and the Fibonacci sequence

Filed under: Geek,Metalog — apotheon @ 02:54

I’ve recently commented on syntax for generating Fibonacci numbers. Slightly more recently, I compared UCBLogo and Perl on the subject of reversing the order of words in a string. I figured I might as well provide examples of UCBLogo, in some context, for generating Fibonacci numbers.

These examples will only generate the final number of a given Fibonacci sequence, and will not output the entire sequence (despite the fact that they tend to need to iterate or recurse through the whole sequence to get to that number, some more explicitly than others). I’ll start by repeating some already presented examples, then go on to the new stuff.


sub fib {
  my ($n, $a, $b) = (shift, 0, 1);
  ($a, $b) = ($b, $a + $b) while $n-- > 0;

Perl (recursion):

sub fib {
  my $n = shift;
  return $n if $n < 2;
  return fib($n - 1) + fib($n - 2);

Python (I’m sure scoth or ToyKeeper will tell me if I screwed it up):

import sys

def fib(): a, b, n = 0, 1, int(sys.argv[1]) while n >= 0: yield a a, b, n = b, a+b, n-1

UCBLogo, inefficient but pretty version:

to fib :n
  if :n<2 [output 1]
  output (fib :n-1)+(fib :n-2)

UCBLogo, succinct but otherwise intermediate version:

to fib :n
  output (cascade :n [?1+?2] 1 [?1] 0)

UCBLogo, verbose but efficient version:

to fib :n
  output first fiblist :n

to fiblist :n if :n<2 [output [1 1]] output newfib fiblist :n-1 end

to newfib :list output fput (sum first :list first butfirst :list) :list end

Just for the extra comparisons, I'll throw in a few more languages, as borrowed from others' code.

PHP (I shudder):

function generatefibonaccisequence( $length ) {
    for( $l = array(1,1), $i = 2, $x = 0; $i < $length; $i++ )
            $l[] = $l[$x++] + $l[$x];

return $l;


Lisp with recursion (of course):

(define fibo
  (lambda (x)
    (if (< x 2)
      (+ (fibo (- x 1)) (fibo (- x 2))))))

Python (yes, more of it, this time with recursion so it's prettier):

def fib(n):
   if   n < 2: return 1
   else      : return fib(n - 1) + fib(n - 2)

Haskell (recursive, obviously):

fib 0 = 0
fib 1 = 1
fib n = fib (n-1) + fib (n-2)

OCaml (described as "a nice closed form" by its contributor on reddit):

let fibonacci n = let phi = ((1. +. sqrt 5.) /. 2.) in
  (intoffloat (((phi ** (floatofint n)) -. 
  ((1. -. phi) ** (floatofint n))) /. sqrt 5.))

let fibs n = let rec fibsi n i = match i with | 0 -> [fibonacci n] | _ -> fibonacci (n - i) :: fibs_i n (i - 1) in fibsi n n;;

Matlab (also from reddit):

([1 1; 1 0]^n)(1,1)

PHP (from reddit, natch):

function fib( $n ){
    return ( $n?2 )
           ? $n
           : fib( $n-1 )+fib( $n-2 );}

HSQL (yes, really -- only on reddit does this stuff arise): Read it HERE, since it's too long to use with code and pre tags without most of it being invisible in your browser if I post it here at SOB. Be forewarned, though, that you may need medical attention after viewing this code, particularly if you're epileptic. (note: Apparently, this code doesn't have anything to do with Fibonacci numbers, according to a commenter here. I really wouldn't know. It just looks like gibberish to me, anyway.)

Comments? Questions? Code snippets in other languages? Improvement to some here? It should be noted that I copied a couple of these things across (or linked to them) without understanding a word of it, like the HSQL. Ugh.


  1. With all the fibonacci fever, a short list of canonical Haskell versions can be found on the Haskell wiki.

    Comment by Don Stewart — 15 December 2006 @ 06:16

  2. Thanks for the link, and for stopping by. I’m slightly surprised you found this place, actually.

    Comment by apotheon — 15 December 2006 @ 09:24

  3. HSQL isn’t a language, it is a library for accessing your SQL database from Haskell. That code snippet doesn’t have anything to do with Fibonacci numbers. And it isn’t formated properly, so it won’t compile (Haskell is layout sensitive), and is overly verbose, since you can omit the type signatures.

    Comment by Joseph Barnes — 20 December 2006 @ 10:01

  4. I didn’t say HSQL was its own language. On the other hand, I apparently made a hasty assumption with regards to its relevance to the Fibonacci problem — thanks for pointing that out.

    Comment by apotheon — 20 December 2006 @ 01:34

  5. […] Over on SOB, apotheon has a couple of posts and some good discussion on Fibonacci sequences in various programming languages. As a combination response to those posts, programming exercise, and lesson in the language – I decided to tackle the problem in Synergy/DE. The download below contains a testing harness and three versions of a Fibonacci number function. […]

    Pingback by Synergy fibs -- Chip’s Tips for Developers — 21 December 2006 @ 05:14

  6. […] In response to apotheon, I created three functions for generating Fibonacci numbers in Synergy/DE. They even have comments. Don’t know why I never needed these sooner. […]

    Pingback by Chipping the web - two forms of pleasure -- Chip’s Quips — 21 December 2006 @ 06:46

RSS feed for comments on this post.

Sorry, the comment form is closed at this time.

All original content Copyright Chad Perrin: Distributed under the terms of the Open Works License