; From: Dat Thuc Nguyen
; Subject: Recursive and Iterative Fibonacci Functions
; Date: Wed, 26 Nov 2003 13:13:58 -0500
; URL: http://www.smalltickle.com
; Adapted and corrected from C-Kermit 8.0 Update Notes, Section 9.
; Reference: Harold Abelson, Structure and Interpretation of Computer Programs
;
echo Recursive...

define FIBONACCI {                                          ; (1)
   (if (== \%1 0) 0
       (if (== \%1 1) 1 (+ (fibonacci (- \%1 2)) (fibonacci (- \%1 1)))))
}

; Time it on fibonacci(17):

.t1 := \v(ftime)
(setq t1 \v(ftime))
(setq result (fibonacci 17))
(setq t2 (- \v(ftime) t1))
echo FIBONACCI(17) = \m(result): TIME = \ffpround(t2,3)

echo Iterative...

define FIBITER {
    (if (== \%3 0) (\%2) (FibIter (+ \%1 \%2) \%1 (- \%3 1)))
}
define FIBONACCI {                                          ; (2)
    (fibiter 1 0 \%1)
}

; Time this one too.

.t1 := \v(ftime)
(setq t1 \v(ftime))
(setq result (fibonacci 17))
(setq t2 (- \v(ftime) t1))
echo FIBONACCI(17) = \m(result): TIME = \ffpround(t2,3)
