Recursion and Bottom up design

In Lisp you can go from simple to very complex solutions. This is possible because of REPL. If you start with something simple and add on top of that simple design you will end up in a better program.



Recursion is a phenomenon in Lisp as it can be used extensively (but should be used judiciously). I was just developing something which required a permutation calculation. Now we know that basic permutation is defined in mathematics as:

P(n) = n! ..... (1)

And permutation of r things from a set of n things is defined as:

P(n)(r) = n! / (n – r)! ..... (2)



And we can expand (1) as:



P(n) = n.(n – 1).(n – 2) …2.1

= n. P( n – 1)



So the following function can be used in Lisp:



(defun permut (x)

( if ( not( eq x 0))

( * x ( permut ( - x 1)))

( block nil ( return 1))))



And from equation (2):



P(n)(r) = P(n)/P( n – r)



We can write this general function as:



(defun permut-n-r(n r)

(/ (permut n) (permut (- n r))))



Here we have used the bottom up approach by defining the easier “permut” function first then moving to the “permut-n-r”.