请输入您要查询的字词:

 

单词 RecursiveFunction
释义

recursive function


Intuitively, a recursive functionMathworldPlanetmath is a positive integer valued function of one or more positive integer arguments which may be computed by a definite algorithmMathworldPlanetmath.

Recursive functions may be defined more rigorously as the smallest class of partial functionsMathworldPlanetmath from +n+ satisfying the following six criteria:

  1. 1.

    The constant function c:++ defined by c(x)=1 for all x+ is a recursive function.

  2. 2.

    The additionPlanetmathPlanetmath function +:+2+ and the multiplication function ×:+2+ are recursive function.

  3. 3.

    The projection functions Imn:+n+ with 1mn defined as Imn(x1,,xn)=xm are recursive functions.

  4. 4.

    (Closure under compositionMathworldPlanetmath) If f:+n+ is a recursive function and gi:+m+ with i=1,n are recursive functions, then h:+n+, defined by h(x1,,xn)=f(g1(x1,,xm),,gn(x1,,xm)) is a recursive function.

  5. 5.

    (Closure under primitive recursion) If f:+n+ and g:+n+2+ are recursive function, then h:+n+1+, defined by the recursion

    h(n+1,x1,,xk)=g(h(n,x1,,xk),n,x1,,xk)

    with the initial condition

    h(0,x1,,xk)=f(x1,,xk)

    is a recursive function.

  6. 6.

    (Closure under minimization) If f:+n+1+ is a recursive function then g:+n+ is a recursive function, where

    • g(x1,,xn) is defined to be y, if there exists a y+ such that

      1. i.

        f(0,x1,,xn),f(1,x1,,xn),,f(y,x1,,xn) are all defined,

      2. ii.

        f(z,x1,,xn)0 when 1z<y, and

      3. iii.

        f(y,x1,,xn)=0.

    • g(x1,,xn) is undefined otherwise.

The operationMathworldPlanetmath whereby h was constructed from f and g in criterion 5 is known as primitive recursion. The operation described in criterion 6 is known as minimization. That is to say, for any given function f:+n+1+, the partial function g:+n+ constructed as in criterion 6 is known as the minimization of f and is denoted by g=μf.

The smallest set of functions satisfying criteria 1-5, but not criterion 6, is known as the set of primitive recursive functionsMathworldPlanetmath. Therefore, the set of all recursive function is the closure of the set 𝒫 of primitive recursive function with respect to minimization. It can be shown that is exactly the set of Turing-computable functions. In terms of programming languages, a function is recursive iff it can be computed by a program involving the DO WHILE loops (minimization).

With some work, it can be shown that the class of recursive functions can be characterized by considerably weaker sets of criteria than those given above. See the entry “alternative characterizations of recursive functions (http://planetmath.org/AlternativeCharacterizationsOfRecursiveFunctions)” for several such characterizationsMathworldPlanetmath.

Titlerecursive function
Canonical nameRecursiveFunction
Date of creation2013-03-22 14:34:35
Last modified on2013-03-22 14:34:35
Ownerrspuzio (6075)
Last modified byrspuzio (6075)
Numerical id27
Authorrspuzio (6075)
Entry typeDefinition
Classificationmsc 03D20
Synonymunbounded minimization
Related topicPrimitiveRecursive
Related topicRecursiveFunctionIsURMComputable
Related topicBoundedMinimization
Definesprimitive recursion
Definesminimization
随便看

 

数学辞典收录了18232条数学词条,基本涵盖了常用数学知识及数学英语单词词组的翻译及用法,是数学学习的有利工具。

 

Copyright © 2000-2023 Newdu.com.com All Rights Reserved
更新时间:2025/5/5 2:05:55