Search code examples
loopsrecursionclisp

Why is there a loop function in (Common) Lisp?

Loops and recursion are of equal power. So why do we have a loop function in functional programming languages like Lisp? Is it because of the stack?

Solution

  • Because some problems/structures are solved more efficiently by iterating over a set of data other by repeatingly performing a certain set of operations. Calculating fibonacci numbers is done more efficiently by iteration than by recursion, simply because it's not a good idea to calculate the same valaues over and over again, even if the stack space is not an issue.

    So this 

    (defun recursive-fib (n)
  (if (<= n 2)
      1
      (+ (recursive-fib (- n 1))
         (recursive-fib (- n 2)))))

    does the same as this

    (defun iterative-fib (n)
  (do ((i n (- i 1)) 
       (fib1 1 (+ fib1 fib2)) 
       (fib2 1 fib1))
      ((<= i 2) fib1)))

    but the second way is much more effcient.