|
Programming Course |
Chapter 5Lisp IV - Repetition and Recursion |
Repetition and iteration constructs cause something to be done a given number of times or to be done to each element in a list of elements. Repetition control structures are said to be one kind of control strategy, which uses conditions to determine how many times to repeat execution of an action.
In an AutoCAD program, the command array can be used to make copies of a drawing object a certain number of times in either rectangular or polar configuration. This is an example of repetition - a command to place copies of a drawing element repeats until specified number of times. In the sequel, various forms are explained in which you can express such control structures.
The while control structure is a repetitive structure with a continuation condition. Its basic form in LISP is:
(while logical_expression
do_expressions
...
)
In this form, the condition specified is checked at the top of the loop. If it is true, all the statements (actions) specified in the body of the loop are executed. This process will stop only when the condition somehow becomes false, otherwise you get a loop that will go on forever - an infinite loop! Usually, one of the actions in the body of the loop does something that causes the condition to evaluate to false.
Examples using numbers.
(defun it_1 (/ N)
(setq N 1)
(while (<= N 10)
(print N)
(setq N (+ N 1))
)
);end of it_1
(defun it_2 (num / M result)
(setq M 1)
(setq result 1)
(while (<= M num)
(setq result (* result M))
(setq M (+ M 1))
)
result
);end of it_2
(defun it_3 (num / N)
(setq N num)
(while (< 0 N)
(print N)
(setq N (- N 2))
)
'DONE
);end of it_3
Examples using lists.
(defun it_4 (lst)
(while lst
(print (car lst))
(setq lst (cdr lst))
)
);end of it_4
(defun it_5 (lst)
(while lst
(if (atom (car lst))
(print (car lst)))
(setq lst (cdr lst))
)
);end of it_5
(defun it_6 (lst1 lst2 / intersection)
(setq intersection nil)
(while lst1
(if (member (car lst1) lst2)
(setq intersection (cons (car lst1) intersection)))
(setq lst1 (cdr lst1))
)
(reverse intersection)
);end of it_6
Examples using AutoCAD commands.
(command "pline" (list 0 0) (list 1 0) (list 1 1) (list 0 1) "c")
(command "block" "square" (list 0 0) "L")
(defun it_7 (M / N)
(setq N 1)
(while (>= M N)
(command "insert" "square" N N 0)
(setq N (+1 N))
)
);end of it_7
The following structures are repetitive structures with a continuation counter. This is quite similar to the while construct except that the number of times the loop should execute is known in advance. This is a safer form of iteration in which it is easy to avoid infinite loops.
(repeat n
do_statements
...
)
Here, the counter is specified as a number. Examples:
(command "circle" "2,2" "1.5")
(setq pt (getpoint "Pick center of rotation: "))
(setq steps (getint "Enter number of steps: "))
(repeat steps (command "rotate" "L" "" pt "3"))
(foreach name list
do_statements
...
)
This form allows iteration on lists. name is assigned each element in list, consecutively. Examples:
(foreach n '(a b c) (print n))
(mapcar function list ...)
mapcar is a function. It applies a function to each element in the list(s) and returns a list of the results of every application. The number of lists must match the number of arguments required by function.
(mapcar ´numberp ´(a 3 b 2 4 c)) => (nil T nil T T nil)
(mapcar ´- ´(2 4 6 8) ´(1 3 5 7)) =>
(mapcar ´car ´((x1 y1)(x2 y2)(x3 y3)))
=>
(mapcar ´(lambda (x)(* 2 x)) ´(1 2 3 4))
=>
(defun dotproduct (v1 v2)
(apply ´+ (mapcar ´* v1 v2))
) =>
(dotproduct ´(1 2 3) ´(2 3 4)) =>
Programs are made up of nested procedures, where one procedure calls another to do part of the work and uses results returned by it. Writing programs as a collection of small functions - also known as modular programming, makes it easier to debug programs. There is another form of procedure that calls upon itself, accumulating results as it goes along - this is known as recursion.
Example: Compute factorial of number n.
(defun factorial (n)
(cond (( = n 1) 1)
(t (* (factorial (- n 1)) n))
)
);end factorial
Simulation of factorial function for n = 3
Factorial 3 = 3 * 2 * 1 = (n * (n - 1) * (n - 2) * ... * 1)
Function call 1: input number 3
Function call 2: input number 2
Function call 3: input number 1
Function call 3: output number 1
Function call 2: output number (2 * 1)
Function call 1: output number (3 * (2 * 1))
In recursive functions, the most important statement is the stop condition, i.e. when the recursive function cannot call itself anymore and thereby avoid infinite recursion.
Recursive functions can get quite complicated and hard to debug. First determine the boundary conditions - when the function cannot call itself anymore, what result it should return, and how to accumulate results.
One way of debugging recursive functions (in fact, all functions in LISP) is by using the built-in predicate trace. You can set a trace on any user defined function and watch it execute. You will be shown actual values of arguments passed to that function when it is invoked, and the value it returns when that function exits.
For example, to trace above function for computing factorials, you should type:
(trace factorial)
And then invoke the function with some argument:
(factorial 3)
Following output shows the result of above two function calls.
(factorial 3)
Entering FACTORIAL: 3
Entering FACTORIAL: 2
Entering FACTORIAL: 1
FACTORIAL - Result: 1
FACTORIAL - Result: 2
FACTORIAL - Result: 6
6
When a procedure calls itself twice with each invocation, it is said to be doubly recursive. The following function is an example of a doubly recursive function. Try to understand the function and see if you can figure out the result it will return.
(defun fibonacci (n)
(cond ((= n 0) 1)
((= n 1) 1)
(t (+ (fibonacci (- n 1)) (fibonacci (- n 2))))
)
);end fibonacci
This exercise gives you an opportunity to use both iteration and recursion control structures in writing a program.
Your program should prompt the user for a width (h_width), a number of sections (n) and a height (hgt1). On each section at the specified height, it should generate a design as shown below. To generate elements on the top, use two more parameters: hgt2 which specifies the height, and offset which specifies the distance between successive divisions in the top element. Note that each element consists of 7 replicas of itself.
Some helpful hints to get you started. Both the bottom
and top portions of the design can be generated using any iterative
structure. For a detailed generation of the elements on top, you
can use a recursive structure. You can define more parameters
if needed in addition to the ones given above. Develop your program
in a modular fashion so that it is easier to debug and test. Put
it all together and submit a single program file, together with
a snapshot of an examplar generation.