An article on recursion

Recursion See "Recursion"

An interesting article on recursion.

Regards,

Mircea

Very interesting indeed! Thanks for sharing

My workstation (P4, 4.3GHz, 2GB RAM) is still computing the AutoLISP version - was started before posted the above. Will post the result later.

(defun fib_rec( n )
(if (< n 2)
 n
(+ (fib_rec (- n 2)) (fib_rec (- n 1)))
)
)

Regards,

Mircea

Is done!

It took 1657 seconds (27 minutes and 37 second) on a P4, 4.3GHz, 2GB RAM.

Regards,

Mircea

I really like his method to use the binary representation of 'n' and successively square the matrix, in LISP this might be:

(defun fib_mat ( n / l a b c )

 (while (< 0 n)
   (setq l (cons (rem n 2) l) n (/ n 2))
 )
 (setq a 1. b 0. c 1.)
 (foreach x l
   (mapcar 'set '(a b c)
     (list (+ (* a a) (* b b)) (+ (* a b) (* b c)) (+ (* b b) (* c c)))
   )
   (if (< 0 x) (setq a b b c c (+ b a)))
 )
 b
)

I suppose the simplest iterative way would be:

(defun fib ( n / a b c)
 (setq a 0. b 1. c 1.)
 (repeat (- n 2) (setq a b b c c (+ a c)))
 c
)

Benchmarking the obvious performance improvements of log2(n) iterations over (n-2) iterations:

_$ (Benchmark '((fib 100) (fib_mat 100)))
Benchmarking .................Elapsed milliseconds / relative speed for 16384 iteration(s):

   (FIB_MAT 100).....1591 / 1.22 <fastest>
   (FIB 100).........1934 / 1 <slowest>

_$ (Benchmark '((fib 1000) (fib_mat 1000)))
Benchmarking ................Elapsed milliseconds / relative speed for 8192 iteration(s):

   (FIB_MAT 1000).....1014 / 7.28 <fastest>
   (FIB 1000).........7379 / 1 <slowest>

Interesting solutions, Lee!

I'm sure that you will enjoy this article also.

Regards,

Mircea

Interesting solutions, Lee!

I'm sure that you will enjoy this article also.

Thanks Mircea, I really enjoyed writing them

That looks like another interesting article, I shall have a read.

Lee

I'm sure that you will enjoy this article also.

Got a chance to read that article the other day, a very interesting read indeed! The majority of his comments are absolutely spot on - especially the part regarding the public perception of mathematicians. Thanks for sharing it.