Recursion bases

  On one of classifications programming languages share on procedural, named also operator or imperative, and declarative languages. The overwhelming majority of programming languages now in use, for example the BASIC, Cobol, Fortran, Pascal, C and Ada, concern procedural languages. The most essential classes of declarative languages are functional, or applied, and logic languages. To category applicateve languages concern, for example Lisp, FP, Apl, Nial, Krc and Logo. The most known language of logic programming is the Prolog.

  In practice programming languages are not purely procedural, functional or logical, and comprise features of languages of various types. On a procedural language it is often possible to write the functional program or its part and on the contrary. Can was instead of language type speak about style or a programming technique more precisely. Naturally various languages support different styles in a different degree.

  The procedural program consists of operators and the sentences controlling of their execution. Typical operators are assignment statements and control transfers, input\output statements and special sentences for the organisation of cycles. It is possible to make fragments of programs of them and the subroutine. At the heart of such programming the capture of value of any variable, fulfilment over it operations and saving of new value by means of the assignment statement and so until then it will not be received yet (and, probably lay, desirable definitive value is printed out).
  The functional program consists of a collection of definitions of functions. Functions, in turn, represent calls of other functions and the sentences controlling of calls. Calculations start with call of some function which in turn calls the functions entering into its definition etc. according to hierarchy of definitions and structure of conditional sentences. Functions it is frequent or direct, or call itself.
  Each call returns some value in the function which has called it, which calculation after that proceeds; this process repeats until then while the function which has started calculation will not return an end result to the user.
  "Pure" functional programming does not recognise assignment and control transfers. The branching of calculations is grounded on the mechanism of processing of arguments of the conditional sentence. Repeated calculations are carried out through the recursion which is the main resource of functional programming.

  Many practical situations assume the recursive or self-repeating behaviour which is coming back to. We will assume, that, for example, we try to read the text in other language, using an explanatory dictionary of this language. When in the text there is an unfamiliar word its explanation is searched in the dictionary. In a word explanation can, in turn, there will be unfamiliar words which need to be found in the dictionary etc. This procedure it is possible to define by means of following rules:

1. Find a word in the dictionary.
2. Read article explaining value of this word.
3. If the explanation is clear, i.e. article does not contain not clear words, continue reading from the last interrupted place.
4. If in an explanation there is an unfamiliar word stop reading, remember a place of the termination and clarify a word meaning, adhering to a collection of rules "word meaning Finding-out".

  The arch represented above corrected name recursive or using as in it the reference to own definition contains. It is a question not of a vicious circle of definitions, and about a line of action which is suitable for usage and we will quite fulfil.

  In the recursive description of operations it makes sense to pay attention to following circumstances. First, procedure contains as a rule terminal branches and a termination condition. Secondly, when procedure reaches a recursive branch functioning process stops also new same process is started from the beginning, but already at new level. The interrupted process somehow is remembered. He will wait and will start to be executed only after the termination of new process. In turn, new process can stop, expect etc.
  So the tree of the interrupted processes from which it is fulfilled only last at the moment time processes (leaflets) is derivated as though; after the termination of their operation process preceding them continues to be fulfilled. Entirely all process is fulfilled, when the tree again will become empty, or, in other words, all interrupted processes will be fulfilled.

  In the real world the recursion appears in the form of various forms and links. It can be both in structure, and in operations.
  Everyone knows the map repeating in two mirrors, installed against each other, the picture representing a picture, the TV in which the TV is visible, etc. In the mathematician recursion meets in connection with many various aspects, such as the rows repeating lines, algorithms, definition and proof procedures, in a word, in the most various structures.
  The recursion meets usually and in the nature: trees have a recursive structure (branches are derivated from other branches), the rivers are derivated from the rivers running into them. Cages share recursively. In plants it is often visible already at macrolevel. For example, seed scales of cones and seeds of some colours (for example, sunflower) are often allocated by the intersected helicoid fans defined by a relation of Fibonacci numbers.
  Life continuation is linked to recursive process. Molecules of DNA and viruses are multiplied, copying themselves, live beings have descendants which, in turn, too has descendants etc.
  The recursion is extended both in language, and in behaviour the same as in ways of a reasoning and knowledge. The recursion in language, for example, can be in structure or in the maintenance:

"Peter has told, that Willy has told, that …"
"I know, that I know, but I do not remember"
"To make; to induce to do; to force, that have induced to do; …"
"Substitute x this sentence"
"Remember and transfer this message"
…

  Musical forms and operations also can be recursive in many respects (for example, a canon in which the tune is accompanied by the same tune with delay, and others).
  The purposeful behaviour and solution of problems are recursive processes. In the same way and researches in the field of an artificial intelligence are recursive in the attempt to research the processes proceeding in a brain with which help there is a research and solution of problems including researches in the field of an artificial intelligence.

  The recursion in Lisp is grounded on the mathematical theory of recursive functions. The recursion well suits for operation with lists as lists can consist of sublists, i.e. have a recursive structure. For processing of recursive structures naturally enough usage of recursive procedures.
  Lists can be defined by means of following rules Backus-Naur:

  The recursion is both in head definition, and in tail definition. We will notice, that the definition brought above directly mirrors definitions of the functions working with lists which can handle recursive call a list head, i.e. "in depth" (in a direction first ), and a tail, i.e. "in width" (in a direction rest).
  Lists can be defined and in the following form which underlines logical recursiveness of construction of lists and atoms and sublists:

  In programming on Lisp the recursion is used for the organisation of repeating calculations. On it splitting of a problem and its sharing into the subtasks, which solution is grounded, how much it is possible, try to reduce to already solved or according to the main idea of recursion to the task solved at the moment.
  On recursion it is grounded and often used at problem solving and by search the mechanism of returns with which help it is possible to return from a deadlock branch to a branching place, having cancelled the done calculations. The recursion in Lisp represents not only the organisation of calculations is a views and problem solving methodology.

  The theory of recursive functions along with algebra of lists and a lambda-calculus is one more support upon which is based Lisp. In this area of mathematics the theoretical questions linked with computable are studied. The computable are understood as such tasks which basically can be programmed and solved by means of the computer. The theory of recursive functions offers along with a Turing machine, a lambda-calculus and others theoretical a formalism equivalent to them algorithmic computable.
  In the theory of recursive functions functions (algorithms) and their properties are considered and classed according to what functions can be received and calculated, using various forms of recursion. The main idea of recursive definition consists that function can be reduced by means of recurrence relations to some initial values, to earlier certain functions or to the most defined function, but with more "simple" arguments. Calculation of such function is ended while it is reduced to known initial values. For example, Fibonacci numbers

  0, 1, 1, 2, 3, 5, …

using infix notation Lisp, it is possible to define by means of following recurrence relations:

  (0 fib) = 0
  (1 fib) = 1
  (n fib) = (((n - 1) fib) + ((n - 2) fib))

  Class of the functions received thus, name as a class of primitively recursive functions.
  There are also the functions which are not primitively recursive. As an example it is possible to bring function Ackerman which can be set following recurrence relations:

  (0 Ack x y) = (y + x)
  (1 Ack x y) = (y * x)
  (2 Ack x y) = (y ^ x)
  …

  ((z + 1) Ack x y) =

to values y x-1 time is applied operation (lambda (u v) (z Ack u v))

  Set by means of brought above the scheme function Ack is not primitively recursive though it and computable, i.e. it can be defined and on the basis of this definition to calculate its value for finite time.
  It is possible to show, that there are the functions which values can be calculated by means of algorithm but which cannot be described algorithmically. Calculation of such function can be infinite. As an example we will bring function (n f m) which result is 1 in case in decimal notation numbers π there is a fragment of repeating digits m in the length n.
  It is possible to show, that the algorithm of calculation of this function exists, but we do not know, what it. We can only try to calculate π signs in hope, that the required fragment will find out, but to define, whether calculation will be completed sometime, we cannot. Such functions are named general-recursive.
  The class primitively recursive functions is interesting enough from the point of view of many practical problems. Application of recursive functions in Lisp is not limited to only numerical arguments, they are used (and even first of all) for character structures that opens new big possibilities in comparison with numerical calculations.