Recursive definition (original) (raw)
تعريف الشيء بنفسه هو تعريفه بما اشتمل على نفس المحدود، كما في قولنا: الإنسان حيوان بشر، فإن تعريف الإنسان مشتمل على البشر، وهو نفس الإنسان.
| Property | Value |
|---|---|
| dbo:abstract | En lògica matemàtica i computació, una definició recursiva (o definició inductiva) s'usa per definir un objecte en termes de si mateix (Aczel 1978:740ff). Una definició recursiva d'una funció defineix els valors de la funció per algunes entrades en termes de valors de la mateixa funció donades diferents entrades. Per exemple, la funció factorial n! es defineix per les regles: 0! = 1.(n+1)! = (n+1)·n!. Aquesta definició és vàlida perquè per tot n, la recursió sempre arriba al cas base 0. Per tant, la definició està ben fundamentada. La definició pot donar-se també com un conjunt de regles que descriuen com construir la funció n!, començant per n = 0 i avançat amb n = 1, n = 2, n = 3, etc. Una definició inductiva d'un conjunt descriu els elements d'un conjunt en termes d'altres elements del conjunt. Per exemple, una definició del conjunt N dels nombres naturals és: 1. * 0 és a N. 2. * Si un element n és en N llavors n+1 és en N. 3. * N és el conjunt més petit que satisfà (1) i (2). Hi ha molts conjunts que satisfan (1) i (2); la clàusula (3) fa la definició precisa triant el conjunt més petit que esdevé N. Les propietats de les funcions i conjunts definides recursivament sovint poden ser provades mitjançant una inducció que segueixi la definició recursiva. Per exemple, la definició dels nombres naturals presentada abans directament implica el principi de la inducció matemàtica pels nombres naturals: si el nombre 0 té si una propietat donada, i si la mateixa propietat la té també un nombre n+1 sempre que també la tingui el nombre n, llavors la propietat donada la tenen tots els nombres naturals (Aczel 1978:742). (ca) تعريف الشيء بنفسه هو تعريفه بما اشتمل على نفس المحدود، كما في قولنا: الإنسان حيوان بشر، فإن تعريف الإنسان مشتمل على البشر، وهو نفس الإنسان. (ar) Una definición recursiva (o definición inductiva) en lógica matemática y ciencias de la computación se utiliza para definir los elementos de un conjunto en términos de otros elementos del conjunto (Aczel 1978:740ff). La definición recursiva de una función define los valores de las funciones para algunas entradas en términos de los valores de la misma función para otras entradas. Por ejemplo, la función factorial n! está definida por las reglas 0! = 1. (n+1)! = (n+1)·n!. Esta definición es válida para todos los n, porque la recursividad finalmente alcanza el caso base de 0. También se puede pensar en la definición como un procedimiento que describe cómo construir la función n!, comenzando desde n = 0 y continuando con n = 1, n = 2, n = 3, etc... El teorema de la recursividad establece que tal definición define efectivamente una función. La prueba utiliza inducción matemática. Una definición inductiva de un conjunto describe los elementos de un conjunto en términos de otros elementos del conjunto. Por ejemplo, una definición del conjunto de números naturales N es: 1. * 1 está en N 2. * Si un elemento n está en N entonces n+1 está también en N. 3. * N es la intersección de todos los conjuntos que satisfacen (1) y (2). Hay muchos conjuntos que satisfacen (1) y (2) - por ejemplo, el conjunto {1, 1.649, 2, 2.649, 3, 3.649, ...} satisface la definición. Sin embargo, la condición (3) especifica el conjunto de números naturales eliminando los conjuntos con elementos extraños. Las propiedades de las funciones y conjuntos definidos recursivamente se pueden probar a menudo mediante un principio de inducción que sigue la definición recursiva. Por ejemplo, la definición de los números naturales presentados aquí implica directamente el principio de inducción matemática para los números naturales: si una propiedad tiene el número natural 0, y la propiedad tiene n+1 cuando tiene n, entonces la propiedad tiene todos los números naturales (Aczel 1978:742). (es) En mathématiques, on parle de définition par récurrence pour une suite, c'est-à-dire une fonction définie sur les entiers positifs et à valeurs dans un ensemble donné. Une fonction est définie par récurrence quand, pour définir la valeur de la fonction en un entier donné, on utilise les valeurs de cette même fonction pour des entiers strictement inférieurs. À la différence d'une définition usuelle, qui peut être vue comme une simple abréviation, une définition par récurrence utilise le nom de l'objet défini (la fonction en l'occurrence) dans la définition même. Le principe de définition par récurrence assure l'existence et l'unicité de la fonction ainsi définie. Il est distinct de celui du raisonnement par récurrence, dont il n'est pas conséquence sans les autres axiomes de Peano. Richard Dedekind l'identifie et en donne une démonstration en 1888 dans son ouvrage Was sind und was sollen die Zahlen ? (« Que sont et à quoi servent les nombres ? »), qui utilise une axiomatisation des entiers dans un cadre ensembliste. Les définitions par récurrence se généralisent aux ordinaux et ensembles bien ordonnés, et plus généralement aux relations bien fondées. On parle également de définition par induction (sur les entiers positifs, sur tel bon ordre, sur les ordinaux, etc.). Elle se généralise aussi aux objets structurés (par exemple les arbres binaires ou les termes), on parle alors de récurrence structurelle ou d'induction structurelle et elle est particulièrement utilisée en informatique pour définir des fonctions (par exemple la taille). (fr) In mathematics and computer science, a recursive definition, or inductive definition, is used to define the elements in a set in terms of other elements in the set (Aczel 1977:740ff). Some examples of recursively-definable objects include factorials, natural numbers, Fibonacci numbers, and the Cantor ternary set. A recursive definition of a function defines values of the function for some inputs in terms of the values of the same function for other (usually smaller) inputs. For example, the factorial function n! is defined by the rules 0! = 1.(n + 1)! = (n + 1)·n!. This definition is valid for each natural number n, because the recursion eventually reaches the base case of 0. The definition may also be thought of as giving a procedure for computing the value of the function n!, starting from n = 0 and proceeding onwards with n = 1, n = 2, n = 3 etc. The recursion theorem states that such a definition indeed defines a function that is unique. The proof uses mathematical induction. An inductive definition of a set describes the elements in a set in terms of other elements in the set. For example, one definition of the set N of natural numbers is: 1. * 1 is in N. 2. * If an element n is in N then n + 1 is in N. 3. * N is the intersection of all sets satisfying (1) and (2). There are many sets that satisfy (1) and (2) – for example, the set {1, 1.649, 2, 2.649, 3, 3.649, ...} satisfies the definition. However, condition (3) specifies the set of natural numbers by removing the sets with extraneous members. Note that this definition assumes that N is contained in a larger set (such as the set of real numbers) — in which the operation + is defined. Properties of recursively defined functions and sets can often be proved by an induction principle that follows the recursive definition. For example, the definition of the natural numbers presented here directly implies the principle of mathematical induction for natural numbers: if a property holds of the natural number 0 (or 1), and the property holds of n+1 whenever it holds of n, then the property holds of all natural numbers (Aczel 1977:742). (en) 再帰的定義（Recursive Definition）は、再帰的な定義、すなわち、あるものを定義するにあたってそれ自身を定義に含むものを言う。無限後退を避けるため、定義に含まれる「それ自身」はよく定義されていなければならない。同義語として帰納的定義（Inductive Definition）がある。 (ja) In matematica una definizione ricorsiva di un insieme A si ha quando per definire A vengono elencati degli elementi di A e delle regole per costruire nuovi elementi di A a partire da elementi di A. Ad esempio l'insieme P dei numeri pari può essere definito ricorsivamente dicendo: * 2 appartiene a P * se un numero n appartiene a P allora anche n+2 appartiene a P Una definizione ricorsiva di una funzione f definita sui numeri naturali si ha quando f viene definita dando esplicitamente il valore che assume su 0 e dando una regola per calcolare il valore della funzione su n a partire dal valore che assume su n-1. Anche in ambiente informatico l'uso della definizione ricorsiva è piuttosto comune, soprattutto sotto forma di acronimo ricorsivo: un esempio molto noto è GNU = GNU's Not Unix dove si può notare come il nome è la parte in un certo senso meno importante della definizione stessa. Infine, l'induzione matematica può portare a una specie di definizione ricorsiva, dove però c'è un caso speciale al quale tutti gli altri prima o poi devono giungere e che quindi fa terminare la ricorsione. Ad esempio, per calcolare il fattoriale di un numero positivo n, si può dire il fattoriale di 1 è 1;il fattoriale di n è n volte il fattoriale di (n-1), se n è maggiore di 1. (it) Рекурсивное определение или индуктивное определение определяет сущность в терминах её самой (то есть рекурсивно), хотя и полезным способом. Для того, чтобы это было возможно, определение в любом данном случае должно быть фундированным, избегая . (ru) Na lógica matemática e em ciência da computação, uma definição recursiva (ou definição indutiva) é usada para definir um objeto em termos de si próprio (Aczel 1977). Uma definição recursiva de uma função define valores das funções para algumas entradas em termos dos valores da mesma função para outras entradas. Por exemplo, a função fatorial n! é definida pelas regras 0! = 1.(n+1)! = (n+1)·n!. Esta definição é valida porque, para todo n, a recursão sempre vai alcançar o caso base de 0. Assim, a definição é bem-fundada. A definição pode também ser vista como um procedimento que descreve como construir a função n!, a partir de n = 0 e prosseguindo em diante com n = 1, n = 2, n = 3 etc.. Uma definição indutiva de um conjunto descreve os elementos de um conjunto em termos de outros elementos no conjunto. Por exemplo, uma definição do conjunto dos números naturais é: 1. * 0 pertence a . 2. * Se um elemento n pertence a então n+1 pertence a . 3. * é o menor conjunto que satisfaz (1) e (2). Há vários conjuntos que satisfazem (1) e (2) - por exemplo, o conjunto {0, 0.649, 1, 1.649, 2, 2.649, 3, 3.649, ...} satisfaz a definição. No entanto, a condição (3) especifica o conjunto dos números naturais, removendo os conjuntos com números externos. Propriedades de funções e conjuntos definidos recursivamente muitas vezes podem ser provadas por um princípio de indução que segue a definição recursiva. Por exemplo, a definição dos números naturais aqui apresentada implica o princípio da indução matemática para os números naturais: se o número natural 0 possui uma propriedade, e n+1 tem a propriedade sempre que n também a possui, então a propriedade é inerente a todos os números naturais (Aczel 1978:742). (pt) Рекурсивне означення (також індуктивне означення) у математичній логіці та інформатиці — задання елементів множин через інші елементи цієї ж множини (Aczel 1978:740). Рекурсивне означення функції встановлює результат функції для деяких параметрів через її ж результат для інших параметрів. Наприклад, функція факторіала n! визначається наступними правилами: 0! = 1.(n+1)! = (n+1)·n!. Дане означення дійсне для всіх n, через те, що в процесі рекурсії врешті-решт досягається початковий варіант 0. Означення можна також розуміти як опис процедури, що визначає функцію n!, починаючи з n = 0 і прогресуючи далі для n = 1, n = 2, n = 3, і т.д. стверджує, що таке означення насправді задає функцію. Доведення ґрунтується на методі математичної індукції. Індуктивне означення множини описує її елементи через інші елементи. Наприклад, означення множини натуральних чисел N: 1. * 1 належить N. 2. * Якщо елемент n належить N, то n+1 також належить N. 3. * N — перетин всіх множин, що задовольняють умовам (1) і (2). Можна сконструювати багато множин, що задовольняють (1) і (2) — наприклад, множина {1, 1.649, 2, 2.649, 3, 3.649, ...}. Однак саме умова (3) визначає множину натуральних чисел, видаляючи всі підмножини, що містять ненатуральні числа. Властивості рекурсивно-означених функцій і множин часто можна вивести з принципу математичної індукції (який слідує рекурсивному означенню). Наприклад, означення натуральних чисел наведене вище напряму містить принцип індукції для натуральних чисел: якщо властивість чинна для натурального числа 0, і властивість чинна для n+1 кожного разу, коли вона чинна для n, тоді властивість чинна для всіх натуральних чисел (Aczel 1978:742). (uk) 递归定义是数理逻辑和计算机科学用到的一种定义方式，使用被定义对象的自身来为其下定义（简单说就是自我复制的定义）。递归定义与归纳定义类似，但也有不同之处。递归定义中使用被定义对象自身来定义，而归纳定义是使用被定义对象的已经定义的部分来定义尚未定义的部分。不过，使用递归定义的函数或集合，它们的性质可以用数学归纳法，通过递归定义的内容来证明。 (zh) |
| dbo:thumbnail | wiki-commons:Special:FilePath/KochFlake.svg?width=300 |
| dbo:wikiPageExternalLink | https://archive.org/details/naivesettheory00halm |
| dbo:wikiPageID | 1047605 (xsd:integer) |
| dbo:wikiPageLength | 9961 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1095408984 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Element_(mathematics) dbr:Base_case_(recursion) dbr:Binomial_coefficients dbr:Definition dbc:Recursion dbr:Jones_&_Bartlett_Learning dbr:Peter_Aczel dbr:Infinite_regress dbr:Mathematical_induction dbr:Mathematics dbr:Function_(mathematics) dbr:Multiplication dbr:Structural_induction dbr:Computer_science dbr:Proposition dbr:1_(number) dbr:Well-order dbr:James_Munkres dbr:Addition dbr:Even_number dbr:Exponentiation dbr:Fibonacci_number dbr:Logical_connective dbr:Well-formed_formula dbr:Recursion dbr:Prime_number dbc:Theoretical_computer_science dbc:Mathematical_logic dbr:Transfinite_recursion dbr:Recursive_data_type dbc:Definition dbr:Circular_definition dbr:Integer dbr:Natural_number dbr:Cantor_set dbr:Recursive dbr:Set_(mathematics) dbr:Factorial dbr:North-Holland_Publishing_Company dbr:Van_Nostrand_Reinhold dbr:File:KochFlake.svg |
| dbp:wikiPageUsesTemplate | dbt:Cite_book dbt:Cite_encyclopedia dbt:Math dbt:Mvar dbt:Reflist dbt:Defining |
| dct:subject | dbc:Recursion dbc:Theoretical_computer_science dbc:Mathematical_logic dbc:Definition |
| rdfs:comment | تعريف الشيء بنفسه هو تعريفه بما اشتمل على نفس المحدود، كما في قولنا: الإنسان حيوان بشر، فإن تعريف الإنسان مشتمل على البشر، وهو نفس الإنسان. (ar) 再帰的定義（Recursive Definition）は、再帰的な定義、すなわち、あるものを定義するにあたってそれ自身を定義に含むものを言う。無限後退を避けるため、定義に含まれる「それ自身」はよく定義されていなければならない。同義語として帰納的定義（Inductive Definition）がある。 (ja) Рекурсивное определение или индуктивное определение определяет сущность в терминах её самой (то есть рекурсивно), хотя и полезным способом. Для того, чтобы это было возможно, определение в любом данном случае должно быть фундированным, избегая . (ru) 递归定义是数理逻辑和计算机科学用到的一种定义方式，使用被定义对象的自身来为其下定义（简单说就是自我复制的定义）。递归定义与归纳定义类似，但也有不同之处。递归定义中使用被定义对象自身来定义，而归纳定义是使用被定义对象的已经定义的部分来定义尚未定义的部分。不过，使用递归定义的函数或集合，它们的性质可以用数学归纳法，通过递归定义的内容来证明。 (zh) En lògica matemàtica i computació, una definició recursiva (o definició inductiva) s'usa per definir un objecte en termes de si mateix (Aczel 1978:740ff). Una definició recursiva d'una funció defineix els valors de la funció per algunes entrades en termes de valors de la mateixa funció donades diferents entrades. Per exemple, la funció factorial n! es defineix per les regles: 0! = 1.(n+1)! = (n+1)·n!. Una definició inductiva d'un conjunt descriu els elements d'un conjunt en termes d'altres elements del conjunt. Per exemple, una definició del conjunt N dels nombres naturals és: (ca) Una definición recursiva (o definición inductiva) en lógica matemática y ciencias de la computación se utiliza para definir los elementos de un conjunto en términos de otros elementos del conjunto (Aczel 1978:740ff). La definición recursiva de una función define los valores de las funciones para algunas entradas en términos de los valores de la misma función para otras entradas. Por ejemplo, la función factorial n! está definida por las reglas 0! = 1. (n+1)! = (n+1)·n!. (es) En mathématiques, on parle de définition par récurrence pour une suite, c'est-à-dire une fonction définie sur les entiers positifs et à valeurs dans un ensemble donné. Une fonction est définie par récurrence quand, pour définir la valeur de la fonction en un entier donné, on utilise les valeurs de cette même fonction pour des entiers strictement inférieurs. À la différence d'une définition usuelle, qui peut être vue comme une simple abréviation, une définition par récurrence utilise le nom de l'objet défini (la fonction en l'occurrence) dans la définition même. (fr) In mathematics and computer science, a recursive definition, or inductive definition, is used to define the elements in a set in terms of other elements in the set (Aczel 1977:740ff). Some examples of recursively-definable objects include factorials, natural numbers, Fibonacci numbers, and the Cantor ternary set. A recursive definition of a function defines values of the function for some inputs in terms of the values of the same function for other (usually smaller) inputs. For example, the factorial function n! is defined by the rules 0! = 1.(n + 1)! = (n + 1)·n!. (en) In matematica una definizione ricorsiva di un insieme A si ha quando per definire A vengono elencati degli elementi di A e delle regole per costruire nuovi elementi di A a partire da elementi di A. Ad esempio l'insieme P dei numeri pari può essere definito ricorsivamente dicendo: * 2 appartiene a P * se un numero n appartiene a P allora anche n+2 appartiene a P Anche in ambiente informatico l'uso della definizione ricorsiva è piuttosto comune, soprattutto sotto forma di acronimo ricorsivo: un esempio molto noto è GNU = GNU's Not Unix (it) Na lógica matemática e em ciência da computação, uma definição recursiva (ou definição indutiva) é usada para definir um objeto em termos de si próprio (Aczel 1977). Uma definição recursiva de uma função define valores das funções para algumas entradas em termos dos valores da mesma função para outras entradas. Por exemplo, a função fatorial n! é definida pelas regras 0! = 1.(n+1)! = (n+1)·n!. Uma definição indutiva de um conjunto descreve os elementos de um conjunto em termos de outros elementos no conjunto. Por exemplo, uma definição do conjunto dos números naturais é: (pt) Рекурсивне означення (також індуктивне означення) у математичній логіці та інформатиці — задання елементів множин через інші елементи цієї ж множини (Aczel 1978:740). Рекурсивне означення функції встановлює результат функції для деяких параметрів через її ж результат для інших параметрів. Наприклад, функція факторіала n! визначається наступними правилами: 0! = 1.(n+1)! = (n+1)·n!. стверджує, що таке означення насправді задає функцію. Доведення ґрунтується на методі математичної індукції. (uk) |
| rdfs:label | تعريف الشيء بنفسه (ar) Definició inductiva (ca) Definición recursiva (es) Definizione ricorsiva (it) Définition par récurrence (fr) 再帰的定義 (ja) Recursive definition (en) Definição recursiva (pt) Рекурсивное определение (ru) 递归定义 (zh) Рекурсивне означення (uk) |
| owl:sameAs | freebase:Recursive definition wikidata:Recursive definition dbpedia-ar:Recursive definition dbpedia-ca:Recursive definition dbpedia-es:Recursive definition dbpedia-fa:Recursive definition dbpedia-fr:Recursive definition dbpedia-he:Recursive definition dbpedia-it:Recursive definition dbpedia-ja:Recursive definition dbpedia-pt:Recursive definition dbpedia-ru:Recursive definition dbpedia-th:Recursive definition dbpedia-uk:Recursive definition dbpedia-zh:Recursive definition https://global.dbpedia.org/id/2KXFX |
| prov:wasDerivedFrom | wikipedia-en:Recursive_definition?oldid=1095408984&ns=0 |
| foaf:depiction | wiki-commons:Special:FilePath/KochFlake.svg |
| foaf:isPrimaryTopicOf | wikipedia-en:Recursive_definition |
| is dbo:wikiPageDisambiguates of | dbr:Definition_(disambiguation) |
| is dbo:wikiPageRedirects of | dbr:Recursively_defined dbr:Inductive_definition dbr:Recursively_define |
| is dbo:wikiPageWikiLink of | dbr:Power_set dbr:Primitive_recursive_function dbr:Schläfli_symbol dbr:Modal_logic dbr:Metamathematics dbr:Metaobject dbr:Binary_tree dbr:Definition dbr:Anti-unification_(computer_science) dbr:List_of_mathematical_logic_topics dbr:Computable_function dbr:Quasi-quotation dbr:Glossary_of_artificial_intelligence dbr:Glossary_of_computer_science dbr:Constructive_set_theory dbr:Recursively_defined dbr:Structural_equation_modeling dbr:Structural_induction dbr:Ordered_pair dbr:B+_tree dbr:Tuple dbr:Lambda_calculus_definition dbr:Liouvillian_function dbr:Robinson_arithmetic dbr:Null_graph dbr:Parity_of_zero dbr:Definition_(disambiguation) dbr:John_Penn_Mayberry dbr:Recurrence dbr:Atomic_formula dbr:Counting_quantification dbr:Term_(logic) dbr:Jensen_hierarchy dbr:Lambda_calculus dbr:Edit_distance dbr:Hereditary_property dbr:Recamán's_sequence dbr:Recursive_data_type dbr:Axiom_schema dbr:BIT_predicate dbr:Circular_definition dbr:Natural_number dbr:Natural_numbers_object dbr:Sequence dbr:Kleene's_recursion_theorem dbr:MU_puzzle dbr:Sardinas–Patterson_algorithm dbr:Literal_(mathematical_logic) dbr:Fixed-point_combinator dbr:Standard_translation dbr:Topological_recursion dbr:Inductive_definition dbr:Recursively_define |
| is foaf:primaryTopic of | wikipedia-en:Recursive_definition |
