Recursion |
|
Recursion occurs where the definition of an entity refers to the entity itself. Recursion can be direct when an entity refers to itself directly or indirect when it refers to other entities which refer to it. A (directly) recursive routine calls itself. Mutually recursive routines are an example of indirect recursion. A (directly) recursive data type contains pointers to instances of the data type. Recursive routines are often simple and elegant and their correctness easily seen. This is particularly true of routines over recursive data types where the structure of a routine follows that of the type. Many mathematical functions are defined recursively and their translation into a programming language is often trivially easy. Recursion is natural in Ada, Algol, C, C++, Haskell, Java, Lisp, ML, Modula, Pascal, Turing and a great many other programming languages. Used carelessly, recursion can sometimes result in an inefficient routine. However there is no necessity for a recursive routine to be less efficient than a non-recursive one. Linear RecursionThe simplest form of recursion is linear recursion. It occurs where an action has a simple repetitive structure consisting of some basic step followed by the action again. See the [Linear recursion page]. Mutual Recursion.In order to check and compile a routine call, a compiler must know the type of the routine, the number of parameters and so on. In direct recursion the routine header which contains this information is seen before any call within the procedure body or later. In mutual recursion the routines must be defined in some order. This means that a call of at least one routine must be compiled before its definition is seen. Different programming languages approach this problem in various ways. Some use separate forward definitions of routine headers to give sufficient information to compile a call and body definitions to contain those calls. See the section on parse-trees for useful examples of mutual recursion. Binary RecursionA binary-recursive routine (potentially) calls itself twice. See the [Binary recursion page]. Edit-Distance Revisited.An earlier section described the dynamic programming algorithm (DPA) which calculates the edit-distance of two strings s1 and s2. This algorithm takes O(|s1|*|s2|) time and space. Hirschberg (CACM 18(6) 341-343 1975) showed that an optimal alignment can be recovered in O(|s1|*|s2|) time and only O(|s2|) space using binary-recursion. See the [O(|s2|)-space page]. N-ary Recursion & PermutationsThe most general form of recursion is n-ary recursion where n is not a constant but some parameter of a routine. Routines of this kind are useful in generating combinatorial objects such as permutations. See the [Permutation page]. PartitionsA partition of a set, S,
is a collection of disjoint sets
See the [Partition page]. N-QueensThe n-queens problem is a classic combinatorial problem. It is required to place n queens on an n*n chess board so that no two queens threaten each other. Therefore no two queens can be on the same row, column or diagonal. There must be a queen on each column and all their row numbers must differ so a solution can be represented as a permutation of the rows. See the [N-Queens page] and also the [3-D N2-Queens] problem. NotesThere are many books on the topic of recursion, e.g.
Exercises
|
|
|