**joseph@hp-pcd.UUCP (joseph)** (08/15/84)

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

**martillo@mit-athena.ARPA (Joaquim Martillo)** (08/17/84)

I meant the shortest recursive version of fib.

**martillo@mit-athena.ARPA (Joaquim Martillo)** (09/08/84)

> 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 > > > I was really interested in fib written in machine language. Writing fib in a higher level language is no challenge and probably compiles to more than 9 instructions.