Recursion or iteration (was Fibonacci series recursion error)

[Ian Kelly]

On Fri, May 13, 2011 at 5:11 AM, rusi <rustompmody at gmail.com> wrote:
> The tightest way I knew so far was this:
> The 2x2 matrix
> 0 1
> 1 1
> raised to the nth power gives the nth fibonacci number. [And then use
> a logarithmic matrix mult]
> Your version is probably tighter than this.

Oh, nice!  I did it this way once:

V = [0 1]

M =
[0 1]
[1 1]

fib(n) = (V * M ** n)[0]

Since I viewed M as operating on V, it never occurred to me that
multiplying by V is actually unnecessary, but it is obvious in
retrospect.  I think it's just a fortuitous coincidence that it works,
since V sets up the base case and M describes the recursive case.  For
a FIbonacci sequence starting with any other pair of numbers, V would
change, but M would not, and so V would no longer happen to be
identical to the top row of M.

Ian