| slovo | definícia |
recursion
(encz) | recursion,rekurze n: Zdeněk Brož |
Recursion
(gcide) | Recursion \Re*cur"sion\ (-sh?n), n. [L. recursio. See Recur.]
The act of recurring; return. [Obs.] --Boyle.
[1913 Webster] |
recursion
(wn) | recursion
n 1: (mathematics) an expression such that each term is
generated by repeating a particular mathematical operation |
recursion
(foldoc) | recursion
mutually recursive
mutual recursion
recurse
recursive
When a function (or procedure)
calls itself. Such a function is called "recursive". If the
call is via one or more other functions then this group of
functions are called "mutually recursive".
If a function will always call itself, however it is called,
then it will never terminate. Usually however, it first
performs some test on its arguments to check for a "base case"
- a condition under which it can return a value without
calling itself.
The canonical example of a recursive function is
factorial:
factorial 0 = 1
factorial n = n * factorial (n-1)
Functional programming languages rely heavily on recursion,
using it where a procedural language would use iteration.
See also recursion, recursive definition, tail recursion.
[Jargon File]
(1996-05-11)
|
recursion
(jargon) | recursion
n.
See recursion. See also tail recursion.
|
| | podobné slovo | definícia |
Recursion
(gcide) | Recursion \Re*cur"sion\ (-sh?n), n. [L. recursio. See Recur.]
The act of recurring; return. [Obs.] --Boyle.
[1913 Webster] |
general recursion theorem
(foldoc) | General Recursion Theorem
Cantor's theorem, originally stated for
ordinals, which extends inductive proof to recursive
construction. The proof is by pasting together "attempts"
(partial solutions).
[Better explanation?]
(1995-06-15)
|
mutual recursion
(foldoc) | recursion
mutually recursive
mutual recursion
recurse
recursive
When a function (or procedure)
calls itself. Such a function is called "recursive". If the
call is via one or more other functions then this group of
functions are called "mutually recursive".
If a function will always call itself, however it is called,
then it will never terminate. Usually however, it first
performs some test on its arguments to check for a "base case"
- a condition under which it can return a value without
calling itself.
The canonical example of a recursive function is
factorial:
factorial 0 = 1
factorial n = n * factorial (n-1)
Functional programming languages rely heavily on recursion,
using it where a procedural language would use iteration.
See also recursion, recursive definition, tail recursion.
[Jargon File]
(1996-05-11)
|
recursion theory
(foldoc) | recursion theory
The study of problems that, in principle, cannot be
solved by either computers or humans.
[Proper definition?]
(1999-03-01)
|
structural recursion
(foldoc) | structural recursion
The process of transforming an expression by expressing its
structure as a syntax tree and applying a certain
transformation rule to each kind of node, starting from the
top. Rules for non-leaf nodes will normally return a result
which depends on applying the rules recursively to its
sub-nodes. Examples include syntax analysis, {code
generation}, abstract interpretation and {program
transformation}.
(1995-01-11)
|
tail recursion
(foldoc) | tail recursion
When the last thing a function (or procedure)
does is to call itself. Such a function is called tail
recursive. A function may make several recursive calls but
a call is only tail-recursive if the caller returns
immediately after it. E.g.
f n = if n < 2 then 1 else f (f (n-2) + 1)
In this example both calls to f are recursive but only the
outer one is tail recursive.
Tail recursion is a useful property because it enables {tail
recursion optimisation}.
If you aren't sick of them already, see recursion and {tail
recursion}.
[Jargon File]
(2006-04-16)
|
tail recursion modulo cons
(foldoc) | tail recursion modulo cons
A generalisation of tail recursion
introduced by D.H.D. Warren. It applies when the last thing a
function does is to apply a constructor functions (e.g. cons)
to an application of a non-primitive function. This is
transformed into a tail call to the function which is also
passed a pointer to where its result should be written. E.g.
f [] = []
f (x:xs) = 1 : f xs
is transformed into (pseudo C/Haskell):
f [] = []
f l = f' l allocate_cons
f' [] p = { *p = nil;
return *p
}
f' (x:xs) p = { cell = allocate_cons;
*p = cell;
cell.head = 1;
return f' xs &cell.tail
}
where allocate_cons returns the address of a new cons cell, *p
is the location pointed to by p and &c is the address of c.
[D.H.D. Warren, DAI Research Report 141, University of
Edinburgh 1980].
(1995-03-06)
|
tail recursion optimisation
(foldoc) | tail recursion optimisation
TRO
(TRO) Discarding the calling environment ({call
stack} frame) when the last thing a function or procedure
does is to call itself. This is important when a procedure
calls itself recursively many times since, without tail
recursion optimisation, the environments of earlier
invocations would fill up the memory only to be discarded when
(if) the last call terminated.
Tail recursion optimisation is a special case of {last call
optimisation} but it allows the further optimisation that some
arguments may be passed in situ, possibly in registers. It
allows recursive functions to be compiled into iterative
loops.
See also conversion to iteration, {tail recursion modulo
cons}.
(2006-04-16)
|
tail recursion
(jargon) | tail recursion
n.
If you aren't sick of it already, see tail recursion.
|
|