In function definition (or more often in definitions of functions calling each other) the recursion can accept various forms. Earlier we have examined simple recursion when the single recursive call of function meets in one or several branches. In this chapter we will continue studying of various forms of recursion, including:
parallel recursion when the body of definition of function f contains a call of some function g, some which arguments are recursive calls of function f:
(… defmethod f …
(… g … (… f …) … (… f …) …) …)
mutual recursion when in function definition f some function g which in turn contains a function call f is called:
(… defmethod f …
(… g …) …)
(… defmethod g …
(… f …) …)
recursion of higher order when argument of a recursive call is the recursive call:
(… defmethod f …
(… f … (… f …) …) …)
Recursion name parallel if it meets simultaneously in several arguments of function.
Let's examine as an example copying of list structure at all levels. Earlier the example of the function copying the list in a direction rest at top level has already been presented: function copy built a copy of a top level of the list. To possible sublists it was not paid attention, and they were not copied, and undertook as well as atoms in that kind as they are (i.e. as the index). If it is necessary to copy the list entirely both in a direction rest, and in a direction first the recursion should extend and on sublists. Thus, we will receive function generalisation copy as copy-tree. The word tree in the function name has arisen because in definition of function the list is treated as a binary tree corresponding to dot pair at which the left subtree corresponds to a list head, and the right subtree - to a tail:
| tree → nil | ; empty tree |
| tree → atom | ; tree leaf |
| tree → ( tree . tree ) | ; dot pair - tree |
>(nil defmethod copy-tree () this)
(lambda nil this)
>('cons defmethod copy-tree ()
(nil cons
((this first) copy-tree) ; head copy
((this rest) copy-tree))) ; tail copy
(lambda nil (nil cons ((this first) copy-tree) ((this rest) copy-tree)))
Function copy-tree differs from copy that the recursion is applied both to a head, and to a list tail. As recursive calls represent two arguments of call of one function (cons) we deal with parallel recursion. We will notice, that parallelism is time as calculation of branches is started simultaneously.
In the same way recursion on a head and a list tail it is possible to check up logic identity of two lists on the basis of comparison of structure and the atoms making the list. We will define further predicate already known to us =:
>('cons defmethod = (x)
(nil if (nil consp x)
(nil if
(nil and
((this first) = (x first)) ; identical heads
((this rest) = (x rest))) ; identical tails
this)))
(lambda (x) (nil if (nil consp x) (nil if (nil and ((this first) = (x first)) ((this rest) = (x rest))) this)))
Let's bring one more example of parallel recursion. We will examine function overturn. This function is intended to overturn of a sequence of elements of the list and its sublists irrespective of their place and depth of an enclosure. Earlier defined by us idle time recursion function reverse turned only list top level:
>(nil defmethod overturn () this)
(lambda nil this)
>('cons defmethod overturn ()
(nil let ((head (nil list ((this first) overturn))))
(nil if (nil atom (this rest))
head
(((this rest) overturn) + head))))
(lambda nil (nil let ((head (nil list ((this first) overturn)))) (nil if (nil atom (this rest)) head (((this rest) overturn) + head))))
>('(a (b (c (d)))) overturn)
((((d) c) b) a)
>('palindrome set '((r a c e) (f a s t) (s a f e) (c a r)))
((r a c e) (f a s t) (s a f e) (c a r))
>(palindrome overturn)
((r a c) (e f a s) (t s a f) (e c a r))
Function overturn turns a list head, forms of it the list and attaches to it in front turned tail.
Applying parallel recursion, it is possible list structure (a binary tree) to press down in the single-level list, i.e. to remove all enclosed brackets. To make it by means of structural transformations difficult enough, but with th help of recursion it is carried out simply:
>(nil defmethod in-one-level ()
(nil if (nil not (nil = this))
(nil list this)))
(lambda nil (nil if (nil not (nil = this)) (nil list this)))
>('cons defmethod in-one-level ()
(((this first) in-one-level) + ; at first a head
((this rest) in-one-level))) ; then a tail
(lambda nil (((this first) in-one-level) + ((this rest) in-one-level)))
>('(a (((((b))))) (c d) e) in-one-level)
(a b c d e)
>((palindrome in-one-level) = ((palindrome overturn) in-one-level))
(r a c e f a s t s a f e c a r)
Function in-one-level unites (function +) the head of the list pressed down in one level and the pressed down tail. If the list head is atom the list as arguments of function + should be lists is formed of it.
The recursion is mutual between two or more functions if they cause each other. For an example it is possible to present function of the manipulation earlier defined by us or mirror reflexion in the form of two mutually recursive functions as follows:
>(nil defmethod overturn () this)
(lambda nil this)
>('cons defmethod overturn ()
(this rearrange nil))
(lambda nil (this rearrange nil))
>(nil defmethod rearrange (result) result)
(lambda (result) result)
>('cons defmethod rearrange (result)
((this rest) rearrange
(nil cons ((this first) overturn) result)))
(lambda (result) ((this rest) rearrange (nil cons ((this first) overturn) result)))
Function rearrange it is used as auxiliary function with additional parametres in the same way, as well as earlier auxiliary function carry was used together with function reverse. In the course of construction of the turned list it cares and of that possible sublists have been turned. It does it not itself, and transfers this work of function specialising on it overturn. The result is received by mutual recursion. Depth and recursion structure depend on a list structure. Except participation in mutual recursion function rearrange it is recursive also in itself.
Corresponding to the enclosed cycles of procedural programming repeated repetitions in functional programming are carried out usually by means of two and more functions, each of which corresponds to a simple cycle. The call of such recursive function is used in definition of other function as argument of its recursive call. Naturally, other recursive call can be argument of a recursive call in function definition. It already will be higher order recursion.
Let's examine at first programming of the enclosed cycles by means of two various functions, and then with the help of higher order recursion. It is possible to express the enclosed cycle and by means of cyclic offers (for, while, etc.) or specialised repeating functions. Such obvious ways we will not use now.
We will start to examine programming of the enclosed cycles from sorting of lists. We will define at first function insert which adds an element a in the ordered list so that orderliness if the order of any two elements is set by a predicate < has remained:
>('cons defmethod insert (a l)
(nil cond
((nil = l)
(nil list a))
((this < a (l first))
(nil cons a l))
(true
(nil cons (l first) (this insert a (l rest))))))
(lambda (a l) (nil cond ((nil = l) (nil list a)) ((this < a (l first)) (nil cons a l)) (true (nil cons (l first) (this insert a (l rest))))))
Predicate < checks, whether there is an element a before an element b, according to an arrangement a certain sequence of elements in the list:
>('cons defmethod < (a b)
(nil cond
((a = (this first)) ; a earlier
true)
((b = (this first)) ; b earlier
false)
(true
((this rest) < a b))))
(lambda (a b) (nil cond ((a = (this first)) true) ((b = (this first)) false) (true ((this rest) < a b))))
>('(a b c d e) < 'b 'e)
true
>('(a b c d e) insert 'b '(a c d))
(a b c d)
insert and < form two-level enclosed iterative structure.
The disorder list can be sorted function sort which recursively puts the first element of the list on a corresponding place in preliminary ordered tail of the list:
>('cons defmethod sort (l)
(nil if (nil consp l)
(this insert (l first)
(this sort (l rest)))))
(lambda (l) (nil if (nil consp l) (this insert (l first) (this sort (l rest)))))
>('(a b c d e) sort '(b a c))
(a b c)
Now recursion of functions sort, insert and < forms already three-level enclosed repeating structure.
Let's bring still function +, function reminding by the structure sort and allowing list elements new to insert into the ordered list l. Function + repeats procedure of an insert for each element of the list new:
>('cons defmethod + (l new)
(nil if (nil = new)
l
(this insert (new first)
(this + l (new rest)))))
(lambda (l new) (nil if (nil = new) l (this insert (new first) (this + l (new rest)))))
>('(a b c d e) + '(a b d) '(b c))
(a b b c d)
This recursive function on arguments can be written down and in the form of function, recursive on value:
('cons defmethod + (l new)
(nil if (nil = new)
l
(this + (this insert (new first) l)
(new rest))))
Expressive recursion possibilities are already visible from the definitions brought above substantial and taking few place. Definitions of functions in-one-level and overturn in an iterative variant would not be located on one sheet of paper (try!). With the help of recursion it is easy to work with dynamic, in advance not defined entirely, but regular enough structures, such as lists of any length and depth of an investment.
Using more and more powerful kinds of recursion, it is possible to write down rather laconic means and more complex calculations. Simultaneously with it as definitions are abstract enough, complexity of programming and understanding of the program grows.
Let's examine now programming of the enclosed cycles in such form at which functions in definition recursive call is argument of call of the same function. In such recursion it is possible to allocate various usages according to at what level of recursion there is a call. Such form of recursion we will name as recursion of higher order. Functions which we defined till now, were functions with recursion of a zero order.
As a classical example of recursion of higher order function Ackermann using glory of "bad" function (differs from classics for convenience a little) is often brought known of the theory of recursive functions:
>('number defmethod ackermann (x y)
(nil cond
((y <= 1)
x)
((this <= 0)
(x + y))
((this = 1)
(x * y))
((this = 2)
(x ^ y))
(true
((this - 1) ackermann x (this ackermann x (y - 1))))))
(lambda (x y) (nil cond ((y <= 1) x) ((this <= 0) (x + y)) ((this = 1) (x * y)) ((this = 2) (x ^ y)) (true ((this - 1) ackermann x (this ackermann x (y - 1))))))
>(0 ackermann 3 3)
6
>(1 ackermann 3 3)
9
>(2 ackermann 3 3)
27
>(3 ackermann 3 3)
7625597484987
Function Ackermann is function with recursion of the first order. Its calculation is complex enough, and calculation time grows as avalanche already at small values of argument.
As other example of function with recursion of the first order we will bring function in-one-level, placing list elements at one level which we have defined earlier, using parallel recursion:
>(nil defmethod in-one-level (result)
(nil if (nil = this)
result
(nil cons this result)))
(lambda (result) (nil if (nil = this) result) (nil cons this result))
>('cons defmethod in-one-level (result)
((this first) in-one-level ((this rest) in-one-level result)))
(lambda (result) ((this first) in-one-level ((this rest) in-one-level result)))
In this definition function work is directly shown to base functions and recursion of the first order where argument of recursive call is one recursive call. In earlier definition in addition to base functions and recursion of a zero order we used function +. Applying recursion of higher order of calculation it is possible to present more abstractly and by means of shorter definition, however to imagine work of such function difficult enough.
Function in-one-level works as follows. The result is under construction in the list result. If this - atom he can be added directly in the list beginning result. If this - the list and its first element is atom all is reduced to the previous condition at a following level of recursion, but in such situation when the list result contains remained tail already extended in one level.
In that case when also the list head is the list it at first lead to one level. It becomes by means of the recursive calls plunging into a head branch until there there will be no atom which can be added in the beginning extended to this moment in one level of structure. Atoms meeting thus are added on one to the extended tail. At each level at list exhaustion on the previous level stands out typed to the given moment result.
Following definition of function reverse, using only base functions and recursion, is an example deeper level of recursion:
(nil defmethod reverse ()
this)
('cons defmethod reverse ()
(nil if (nil consp (this rest))
(nil cons
(((this rest) reverse) first)
((nil cons
(this first)
((((this rest) reverse) rest) reverse))
reverse))
this))
In definition it is used the second order recursion. The calculations presented by this definition to understand more difficultly, than former. Complex recursion complicates also calculations. In this case it is impossible to take advantage again of the results received earlier, therefore the same results should be calculated again and again. Reversing of the list with five elements function reverse demands 149 calls. The ten-element list demands already 74409 calls and appreciable time for calculation! As a rule, repeated calculations can be avoided, having broken definition on some parts and using suitable parametres for preservation and transfer of intermediate results.
Usually in practical programming of the form of recursion of higher order are not used, but they at least have a theoretical and methodological value.