Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Posting-Version: notesfiles - hp 1.2 08/01/83; site hp-pcd.UUCP
Path: utzoo!watmath!clyde!burl!mgnetp!ihnp4!zehntel!hplabs!hp-pcd!joseph
From: joseph@hp-pcd.UUCP (joseph)
Newsgroups: net.math
Subject: Re: Shortest Fib in Machine Language (Co
Message-ID: <13900002@hp-pcd.UUCP>
Date: Tue, 14-Aug-84 18:15:00 EDT
Article-I.D.: hp-pcd.13900002
Posted: Tue Aug 14 18:15:00 1984
Date-Received: Fri, 24-Aug-84 04:46:53 EDT
References: <249@mit-athe.UUCP>
Organization: Hewlett-Packard - Corvallis, OR
Lines: 14
Nf-ID: #R:mit-athe:-24900:hpcvlo:13900002:000:450
Nf-From: hpcvlo!joseph    Aug 20 14:15:00 1984


    Probably the shortest recursive routine is:

    function fib(n : integer) : integer;
    begin
     if n < 2 then fib := 1
     else fib := fib(n-1) + fib(n-2);
    end;

    However, this requires exponential time.

    (time is proportional to g**n  where g is the golden ratio, 1 + sqrt(5)
                                                                ------------
                                                                      2