Simple recursion

  Function is recursive if in its definition call of most this function contains. We will speak about recursion on value when call is the expression defining result of function. If as result of function value of some other function and recursive call comes back participates in calculation of arguments of this function we will speak about recursion on arguments. Again recursive call can be argument of recursive call, and such calls can be much.

  Let's consider at first a case of simple recursion. We will say, that recursion simple if function call meets in some branch only once. To simple recursion in procedural programming there corresponds an ordinary cycle.
  Let's define methods copy which builds a list copy. The list copy is logically identical to the initial list:

>(nil defmethod copy () this) ; reaching of the end of the list
(lambda nil this)
>('cons defmethod copy ()
   (nil cons (this first) ((this rest) copy))) ; recursion
(lambda nil (nil cons (this first) ((this rest) copy)))
>('l set '(a b c))
(a b c)
>(l copy)
(a b c) ; logical copy
>(nil eq l (l copy))
false ; physically various lists

  This method is recursive on argument as recursive call stands on a place of argument of function cons . The method passes the list, copying and shortening in the course of it the list after a direction rest. The branch with the recursion termination is reached by that the method copy virtual and at reaching of the end of the list returns nil. After that recursive calls will be ended and come back by turns to the previous levels, and by means of function cons in a recursive branch of definition the new list will start to be formed from the end to the beginning. At each level to a tail returned from the previous level (this rest) the head part from current level (this first) is added.
  Pay attention, that function copies not list units (i.e. in a direction first, or in depth), and cells of a top level only making the list (i.e. the list is copied in a direction rest, or in width). To copy the list on any depth it is necessary to add only one more recursive call.
  Copying of lists represents one of the main operations over lists and consequently appropriate function is included into number of the built in methods.

  The recursion can be used for definition as predicates, and functions. As the second application of simple recursion we will take built in predicate Lisp contain. With its help it is possible to check up, whether some unit belongs to the given list or not.

>(nil defmethod contain (a) false) ; the list is empty ?
(lambda (a) false)
>('cons defmethod contain (a)
  (nil if ((this first) = a)
    this ; a is found ?
    ((this rest) contain a))) ; a - at the tail-end ?
(lambda (a) (nil if ((this first) = a) this ((this rest) contain a)))
>('(a b c d) contain 'b)
(b c d)
>('(a b c d) contain 'e)
false

  In the course of calculations arises three situations:

1. The list is empty or from the very beginning or because list review is ended.
2. ((this first) = a)
   The first unit is the required unit. As result the list, in which a - the first unit comes back.
3. ((this rest) contain a)
   Or the unit contains in a tail, or does not enter at all into the list. This task is similar initial, only it is less on size. Therefore we can use the same mechanism for its solution, or, in other words, apply a predicate to a tail.

  If the list is empty or a in it does not enter, function returns value false. Otherwise it returns that part of the list in which required a is the first unit as the value. This distinct from false and nil expression corresponds to logical value "true".

  In predicate definition contain the initial task is divided on two subtasks. The first is reduced to simple conditions of the termination. The second solves the same task, but on step shorter. Its solution can be reduced recursively to the function solving the initial task.
  Predicate contain calculation looks so:

>('(a b c d) contain 'c)

  At first two levels of recursion of calculation are carried out on the second, recursive branch. In recursive call by argument is c, as a required unit on each step same. The object takes a tail of current level (this rest).
  At the third level value of a predicate ((this first) = a) becomes c, therefore at this level value of appropriate expression yielding result this = (c d) becomes value of all call. This value comes back to the previous level where it will be value of call contain in a recursive branch and, thus, becomes value of all call at the second level. Further this value comes back further to level and, eventually, is output to the user.
  In the course of descent on a recursion course on more low levels value of parametre a does not vary, while value this varies at transition to the following level. Values of the previous level are saved, as links of variables associate with level. Values of the previous levels are hidden until on them control after that old links become again active will not return. In the brought example after return on the previous levels these links are not used. Pay attention, that parametre links a at various levels are physically various, though value remains to the same.

  Absence of check, erratic condition or their incorrect order can lead to infinite recursion. It would happen, for example, if in a predicate contain value of the object was not shortened continually recursions by the form (this rest). The same would happen, if the recursive branch was in the conditional sentence before a termination condition. Therefore it is essential, that each step of recursion approximated calculations to a termination condition.
  In practice recursive calculations cannot appear infinite as each recursive call demands a memory quantity, and the memory total amount is limited. At simple recursion memory is filled fast, but in more difficult cases of calculation can appear practically infinite, in other words, before memory exhaustion will is useless machine time is spent a lot of.

  Let's consider the intrinsic function +, uniting two lists in one new list. Function +, like function copy, builds the new list of the values saved at various levels of recursion:

>(nil defmethod + (x) x)
(lambda (x) x)
>('cons defmethod + (x)
   (nil cons (this first) ((this rest) + x)))
(lambda (x) (nil cons (this first) ((this rest) + x)))

  Let's give an example:

>('(m e r) + '(g e))
(m e r g e)
>('(a b) + nil)
(a b)
>('(a b nil) + '(nil))
(a b nil nil)

  The idea of operation of function consists that function calls cons with list units are recursively postponed until it will not be exhausted, then as result the pointer comes back to the list x and the postponed calls, completing the operation, form result:

>('(a b) + '(c d))

  Pay attention, that the list is under construction from the end of the first list to the beginning as function calls calculated in the course of recursion cons start to be calculated from depth outside as process of return of recursion is carried out.
  Apparently from the given definition, + copies the list which is the object. This function can be used in sort (list + nil) when it is necessary to make a copy of a top level of the list. But all the same it is better to use the form (list copy).

  All previous definitions of functions contained only one recursive call. We will consider as a following example the intrinsic function containing two recursive branch remove which deletes from the list all coinciding with the given atom (using a method =) units and returns as value the list from all remained units. Remove it is possible to define through basic functions and her as follows:

>(nil defmethod remove)
(lambda)
>('cons defmethod remove (x)
  (nil if (x = (this first))
    ((this rest) remove x) ; have removed a unit
    (nil cons (this first) ; creation of the new list
      ((this rest) remove x))))
(lambda (x) (nil if (x = (this first)) ((this rest) remove x) (nil cons (this first) ((this rest) remove x))))
>('(d i c e) remove 'd)
(i c e)
>('(a (b c)) remove 'b) ; units are checked only in a direction rest
(a (b c))
>('((a b) (c d)) remove '(a b))
((c d)) ; matching =

  The list is reduced by deleting of all identical x in sense = units and copying in the list of other units until the list end will be reached. The result is formed in the course of return of similarly function +.

  Function substitute, substituting all occurrences of the given unit old in the list on a unit new, works like function remove.

>(nil defmethod substitute)
(lambda)
>('cons defmethod substitute (old new)
  (nil cons
    (nil if ((this first) = old)
      new ; head replacement
      (this first)) ; the head does not vary
    ((this rest) substitute old new))) ; tail processing
(lambda (old new) (nil cons (nil if ((this first) = old) new (this first)) ((this rest) substitute old new)))
>('(a x x a) substitute 'x 'b)
(a b b a)

  Pay attention, as here replacement is made only at the uppermost level of the list, i.e. the recursion is carried out only by a tail part of the list (in a direction rest). As well as at copying of the list procedure of replacement of a unit can be generalised so that the list was handled and in depth, for this purpose in a case when the list head is the list, it is necessary to carry out recursion and by a head part.

  In the brought examples we viewed the list according to a direction of pointers in list cells from left to right. But what to make, if it is necessary to handle the list from right to left, i.e. from the end to the beginning?
  Let's consider for an example function reverse which also is the intrinsic function. Reverse changes an order of units in the list (on a top level) on the return.
  For tumbling of the list we should reach its last unit and put its first unit of the paid list. Though directly end of the list is not accessible to us, it is possible, using + to describe necessary operations. The idea of definition consists in the following: we take the first unit of the list (this first), we make of it by means of call (nil list (this first)) the one-element list and we unite its function + with the inverted tail. The tail at first accesses recursive call ((this rest) reverse).

>(nil defmethod reverse)
(lambda)
>('cons defmethod reverse ()
  (((this rest) reverse) + (nil list (this first))))
(lambda nil (((this rest) reverse) + (nil list (this first))))
>('(a b c) reverse)
(c b a)
>('((a b) (c d)) reverse)
((c d) (a b)) ; overturns only the first level

  To reach the last unit of the list it is possible, only having passed the chain derivating the list from left to right. reverse the list will pass in function up to the end and on path suitable units of the list are postponed in arguments of not complete calls. Construction of the paid list in an order opposite to following of units of the initial list can is started only after recursion end. The result will be generated, when the stack of recursive calls will be exhausted.

  The list is nonsymmetric data structure which will be simple to pass from left to right. In many cases the calculations made from right to left are more natural to task solution. For example, the same tumbling of the list would be much easier for carrying out, if immediate access to the last unit of the list was possible. Such inconsistency between data structure and process of solution of the task leads to difficulties of programming and can be for the inefficiency reason.
  In programming procedural languages there is a possibility of usage of auxiliary variables in which it is possible to save subproducts. For example, list call can be carried out simple carrying over of units of the list one after another in the list, using function cons:

>(nil defmethod reverse)
(lambda)
>('cons defmethod reverse ()
  (nil let ((rest this)
      result)
    (nil do-while
      ('result set (nil cons (rest first) result))
      ('rest set (rest rest)))
    result))
(lambda nil (nil let ((rest this) result) (nil do-while ('result set (nil cons (rest first) result)) ('rest set (rest rest))) result))

  In functional programming variables thus are not used. But the appropriate mechanism can be carried out easily, using auxiliary function for which the necessary auxiliary variables are parametres. Then for function reverse we will receive such definition:

>(nil defmethod reverse)
(lambda)
>('cons defmethod reverse ()
  (this carry nil))
(lambda nil (this carry nil))
>(nil defmethod carry (result)
  result)
(lambda (result) result)
>('cons defmethod carry (result)
  ((this rest) carry (nil cons (this first) result)))
(lambda (result) ((this rest) carry (nil cons (this first) result)))

  Auxiliary function carry is recursive on value as to resultants expression of its body is directly recursive call. By means of this function units are transferred in such a manner that on each step of recursion the next unit passes from result. The paid list is under construction a unit behind a unit function cons in argument result the same as and in an iterated variant. Calculations are made under the list from left to right and correspond to iterated calculations.