My 1981 book LISP (ISBN 0-201-08329-9) taught me about recursive programming, and here below is an example (tower-of-hanoi), which I programmed into my Sinclair Spectrum 48k in about 1986, since when I have taken a great deal of interest in Artificial Intelligence, which was what LISP was designed as a Symbol Manipulation Language to do. There is an example in the book of visual recognition used in Industry, where Engineers have been able to shift one type of package from one route to another, thus avoiding mixing of many different types of package, and segregating them more usefully - like the Post Office used to do, before Royal Mail started up. Below is a page from that LISP book, showing one object that could be sorted on a conveyor belt of goods:
and the book shows several short LISP programmes for determining the Area (15 lines of code), Centre of Area (24), Orientation (of least inertia, 36), Perimeter Length (20), and Euler number (identifies whether holes exist in image, 22) for any image, not just this one, and thus to identify the object, whether it be a banana, a tomato, a mushroom, a hammer, a screwdriver, a small or a big box, a silicon chip, an address,.......
That LISP book also taught me about how I think, for it chose to display search trees on page 138 and I adopted diagram (c) which I show here below: I think Depth First - which is my (and Engineering's) normal pattern. That is from Requirement A to think down design routes B C D and then B E and to ensure we have thought of everything, we would go down F G H and then F G J thus to complete a full in depth design alternatives with development timescales, resources and man-hours costs. This diagram assumes I have presented ALL of the alternatives of course! Commercial Department would translate this into £ notes required, and put their contract around our Definition Submission - like the MilSpec we did for the Tornado Engine, the RB199 in 1969.
Note that Politicians will normally be asked to remember many Policies, so will go on a Breadth First route for they cannot know the Depth First route - hence they will remember D H J perhaps, but will have no knowledge, or even idea, of how it got there, whilst I might remember the most important route, but not necessarily all the alternatives unless I take some time to explore my memory by logically remembering the evaluation.
This RECURSIVE programme (tower-of-hanoi) certainly works, as follows, from design to execution:
*(DEFUN tower-of-hanoi (N) (transfer 'A 'B 'C N))
; N discs on A first, smaller disc always on top of bigger
; and throughout never have a bigger disc on top of a smaller disc
; the aim is to move all discs in order from column A to B
; this is a comment and takes no part in the programme
*(DEFUN move-disc (FROM TO)
(LIST (LIST 'move 'disc 'from FROM 'to TO)))
*(DEFUN transfer (FROM TO SPARE NUMBER)
(COND ((EQUAL NUMBER 1) (move-disc FROM TO)
(T (APPEND (transfer FROM SPARE TO (SUB1 NUMBER)) ;recursive
(move-disc FROM TO)
(transfer SPARE TO FROM (SUB1 NUMBER)))))) ;recursive
;The software will expect this type of instruction from the keyboard:
*(tower-of-hanoi 3) ;and then will print:
((move disc from A to B)(move disc from A to C)(move disc from B to C)(move disc from A to B)*(move disc from C to A)(move disc from C to B)(move disc from A to B))
;or, given a new move-disc function:
*(DEFUN move-disc (FROM TO)
(LIST FROM TO))
;the keyboard instruction:
*(tower-of-hanoi 5) ;will give column-column:
(AB AC BC AB CA CB AB AC BC BA CA BC AB AC BC AB CA CB AB CA BC BA CA CB AB AC BC AB CA CB AB)
; where the column of discs on A has now been entirely and correctly moved to B
*(TRACE transfer) ; this will trace each use of the function transfer
*(TRACE move-disc) ; this will trace each use of the function move, then:
*(tower-of-hanoi 3) ;is traced as follows:
0: (transfer A B C 3)
1: (transfer A C B 2)
2: (transfer A B C 1)
3; (move-disc A B)
3: (move-disc returned (AB))
2: (transfer returned (AB))
2: (move-disc A C)
2: (move-disc returned (AC))
2: (transfer B C A 1)
3: (move-disc B C)
3: (move-disc returned (BC))
2: (transfer returned (BC))
1: (transfer returned (AB AC BC))
1: (move-disc A B)
1: (move-disc returned (AB)
1: (transfer C B A 2)
2: (transfer C A B 1)
3: (move-disc C A)
3: (move-disc returned (CA))
2: (transfer returned (CA))
2: (move-disc C B)
2: (move-disc returned (CB))
2: (transfer A B C 1)
3: (move-disc A B)
3: (move-disc returned (AB))
2: (transfer returned (AB))
1: (transfer returned (CA CB AB))
0: (transfer returned (AB AC BC AB CA CB AB))
(AB AC BC AB CA CB AB)
*
