Kapitel 7

Lisp IV: Iteration und Recursion

7.1 Repetition and Iteration

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 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 following are explained various forms in which you can express such control structures.

7.1.1 While

The basic form of while control structure is:

(while some_condition_is_true

do_some_action1

do_some_action2

...

)

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 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

7.1.2 Repeat

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.

(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"))

7.1.3 Foreach

This form allows iteration on lists.

(foreach n '(a b c) (print n))

7.2 Recursion

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.

7.2.1 Trace

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

.c3. 7.2.2 Double Recursion

When a procedure calls itself twice with each invocation, it is said to be doubly recursive. 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

A small program illustrating recursion is available in the file 0 7_demo.lsp in directory /homes2/prog/ausgabe. Copy the file in your account and load it into AutoCad.

7.3 Uebung 7

This exercise gives you an opportunity to use both iteration and recursion control structures in writing a program.

Your program should prompt a user for width (h_width), number of vertical divisions (n) and height (hgt1). On each division 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 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 detailed generation of elements on top, you can use 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 program file saved as 07_name.lsp. Copy your program file into directory /homes2/prog/abgabe.

To the next chapter
Prog Content Vorwort ..1.. ..2.. ..3.. ..4.. ..5.. ..6.. ..7.. ..8.. ..9.. ..10.. ..11.. ..12.. ..13.. Appendix

@ by Architektur und CAAD 1994.......... The Teacher Team