One of the oldest most visited problems in any computer science course the Fibonacci series a very good explanation including sample algorithms can be found in the almighty Wikipedia

This program presents a slight extension in that you can calculate series formed by the sum of the k prior elements. All you have to do is change the size of the array that stores the k prior numbers.

There is just a little trick to work out in which element of the array will the nth element be stored.

;working array of only two el elements

;If the array is initialised to k the program will calculate series or order k

;That is f(i)=f(i-1)+...+f(i-k) when k=2 its the Fibonacci series

(setq arr (make-array 2))

;initialising the array

; builds the first array for k as (0 ... k)

(dotimes (i (array-dimension arr 0))

(setf (aref arr i ) i )

)

;function summing all the elements in the array

(defun sum (vect)

(setq temp 0)

(dotimes (i (array-dimension arr 0))

(setq temp (+ temp (aref vect i )))

)

(setq sum temp)

)

;function calculating the fibbonaci-k series without recursion

(defun fib(pos)

(setq buffSize (array-dimension arr 0 ))

(dotimes (i pos)

(setq j (mod i buffSize))

(setf (aref arr j) (sum arr))

)

(setq extract (mod (- pos 1) (array-dimension arr 0)))

(setq fib (aref arr extract))

)

(print '(I will calculate for you the nth fibonacci number n= ) )

(setq num (read))

(print '(using k=))

(print (array-dimension arr 0))

(setq res (fib num))

(print res)

;(print arr)

This is one of the typical algorithms that gains alot from being de-recursified. Like this the memory footprint is low, the computation time also, as we only add a modulus operation, and everyone is happy.