Bases of recursion

  On one of classifications programming languages share on procedural, named also operational or imperative, and declarative languages. The overwhelming majority of now in use programming languages, for example the BASIC, Cobol, Fortran, Pascal, C and Ada, concern to procedural languages. The most essential classes of declarative languages are functional, or applied, and logic languages. To a category of functional 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 cleanly procedural, functional or logic, and comprise features of languages of various types. In procedural language it is often possible to write the functional program or its part and on the contrary. Can was instead of type of language speak about style or a method of programming more precisely. Naturally various languages support different styles in a different degree.

  The procedural program consists of sequence of operators and the offers operating sequence of their performance. Typical operators are operators of giving and transfer of management, operators of input-output and special offers for the organization of cycles. It is possible to make fragments of programs of them and subroutines. In a basis of such programming the capture of value of any variable, fulfilment above it of action and preservation of new value by means of the operator of giving and so until then it will not be received yet (and, probably lay, desirable final value is printed).
  The functional program consists of set of definitions of functions. Functions, in turn, represent calls of other functions and the offers operating sequence of calls. Calculations begin with a call of some function which in turn causes the functions entering into its definition, etc. according to hierarchy of definitions and structure of conditional offers. Functions often or directly, or not cause themselves.
  Each call returns some value in the function which has caused it, which calculation after that proceeds; this process repeats until then while started functions evaluations will be not not returned with an end result to the user.
  "Pure" functional programming does not recognize givings and transfers of management. The branching of calculations is based on the mechanism of processing of arguments of the conditional offer. Repeated calculations are carried out through recursion, being by the basic means of functional programming.

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

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

  The arch represented above corrected name recursive or using itself as in it the reference to own definition contains. It is a question not of a vicious circle of definitions, and about an image of actions which is suitable for use and we shall quite execute.

  In the recursive description of actions it is meaningful to pay attention to following circumstances. First, procedure contains as a rule terminal branches and a condition of the termination. Secondly, when procedure reaches a recursive branch functioning process stops also new same process is started from the beginning, but already at a new level. The interrupted process somehow is remembered. It 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 carried out only the last at the moment time processes (leaflets) is formed as though; after the termination of their work process preceded them continues to be carried out. Entirely all process is executed, when the tree again will become empty, or, in other words, all the interrupted processes will be executed.

  In the real world recursion is shown in the form of various forms and communications. It can be both in structure, and in actions.
  Everyone knows the image repeating in two mirrors, established against each other, a picture representing a picture, the TV in which the TV, etc. In the mathematician recursion meets in connection with many various aspects is visible, such as the numbers, repeating lines, algorithms, procedures of definition and the proof, in a word, in the most various structures.
  Recursion meets usually and in the nature: trees have a recursive structure (branches are formed of other branches), the rivers are formed of the rivers running into them. Cells share recursively. In plants it is often visible already at a macrolevel. For example, seed scales cone and seeds of some colors (for example, sunflower) are often located by the crossed helicoid fans defined by a parity of numbers Fibonachy.
  Continuation of a life is connected with recursive process. Molecules of DNA and viruses are made multiple copies, copying themselves, alive essences have posterity which, in turn, too has posterity, etc.
  Recursion is widespread both in language, and in behaviour the same as in ways of a reasoning and knowledge. 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; …"
"Replace x with this sentence"
"Remember and transfer this message"
…

  Musical forms and actions also can be recursive in many respects (for example, a canon in which the melody is accompanied by the same melody with a delay, and others).
  The purposeful behaviour and the decision of problems are recursive processes. In the same way and researches in the field of an artificial intellect recusive in the attempt to investigate the processes proceeding in a brain by means of which there is a research and the decision of problems including researches in the field of an artificial intellect.

  Recursion in Lisp is based on the mathematical theory of recursive functions. Recursion well approaches for work with lists as lists can consist of sublists, i.e. have a recursive structure. For processing recursive structures naturally enough use of recursive procedures.
  Lists can be defined by means of following rules Backus-Naur:

  Recursion is both in definition of a head, and in definition of a tail of the list. We shall notice, that the definition resulted above directly reflects definitions of the functions working with lists which can process a recursive call a head of the list, i.e. "in depth" (in a direction first), and a tail of the list, i.e. "at width" (in a direction rest).
  Lists can be defined and in the following form which emphasizes logic recursiveness of construction of lists and atoms and sublists:

  In programming on Lisp recursion is used for the organization of repeating calculations. Splitting a problem and its division into subtasks, which decision is based on it, how much it is possible, try to reduce to already solved or according to the basic idea of recursion to a problem solved at the moment.
  On recursion is based and often used at the decision of problems and by search the mechanism of returns by means of which it is possible to return from a deadlock branch to a place of a branching, having cancelled the done calculations. Recursion in Lisp represents not only the organization of calculations is a views and methodology of the decision of problems.

  The theory of recursive functions alongside with algebra of lists and lambda-calculation is one more support upon which is based Lisp. In this area of mathematics the theoretical questions connected with computable are studied. Under computable such problems which basically can be programmed and solved by means of the computer are understood. The theory of recursive functions offers alongside with machine Tjuringa, lambda-calculation and others theoretical a formalism equivalent to them algorithmic computable.
  In the theory of recursive functions (algorithms) and their properties are considered and classified according to what functions can be received and calculated, using various forms of recursion. The basic idea of recursive definition consists that function can be reduced by means of recurrent formulas to some initial values, to earlier certain functions or to the most defined function, but with more "simple" arguments. Calculation of such function comes to an end during that moment when it is reduced to known initial values. For example, numbers Fibonachi

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

Using infix Lisp notation, it is possible to define by means of following recurrent formulas:

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

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

  (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 resulted 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 final time.
  It is possible to show, that there are 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 shall result function (n f m) which result is 1 in case in decimal record of number π there is a fragment from sequence of repeating figures 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 sequence will be found out, but to define, whether calculation will end sometime, we cannot. Such functions refer to general-recursive.
  The class of 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 symbolical structures that opens new greater opportunities in comparison with numerical calculations.