Кіріспе
Жинақтың элементтерін жиынның басқа элементтері арқылы анықтау. Математика мен компьютерлік ғылымда жиынның элементтерін жиынның өзге элементтері арқылы анықтау үшін рекурсивті анықтама немесе индуктивті анықтама қолданылады (Aczel 1977:740ff). Рекурсивті анықталатын объектілердің мысалдарына факториалдар, натурал сандар, Фибоначчи сандары және Кантор үштік жиыны жатады. Функцияның рекурсивті анықтамасы функцияның кейбір кіріс мәндерін сол функцияның басқа (әдетте кішірек) кіріс мәндері арқылы анықтайды. Мысалы, n! факториал функциясы келесідей анықталады:
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
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 1=n = 0 and proceeding onwards with 1=n = 1, 2, 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 is in \N. If an element n is in \N then n + 1 is in \N. \N is the smallest set 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. 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).
Бұл анықтама кез келген натурал сан n үшін жарамды, себебі рекурсия ақырында 0 негізгі жағдайына жетеді. Анықтаманы n! функциясының мәнін есептеу процедурасы ретінде де қарастыруға болады, 1=n=0-ден бастап, 1=n=1, 2, 3 және т.б. арқылы жүре отырып. Рекурсия теоремасы мұндай анықтама шындығында бірегей функцияны анықтайды деп мәлімдейді. Дәлелдеме математикалық индукция қолданады. Жинақтың индуктивті анықтамасы жиынның элементтерін жиынның басқа элементтері арқылы сипаттайды. Мысалы, \N натурал сандар жиынының бір анықтамасы: 1 \N-ге жатады. Егер n элементі \N-ге жатса, онда n + 1 \N-ге жатады. \N – (1) және (2) шарттарын қанағаттандыратын ең кіші жиын. (1) және (2) шарттарын қанағаттандыратын көптеген жиындар бар – мысалы, {1, 1.649, 2, 2.649, 3, 3.649, } жиыны да анықтаманы қанағаттандырады. Дегенмен, (3) шарты натурал сандар жиынын артық мүшелері бар жиындарды алып тастау арқылы нақтылайды. Рекурсивті анықталған функциялар мен жиындардың қасиеттерін көбінесе рекурсивті анықтамаға сәйкес келетін индукция принципі арқылы дәлелдеуге болады. Мысалы, осы жерде ұсынылған натурал сандардың анықтамасы тікелей натурал сандарға қатысты математикалық индукция принципін білдіреді: егер қасиет натурал сан 0 (немесе 1) үшін орындалса, және қасиет n үшін орындалса, онда ол n + 1 үшін де орындалады, сонда қасиет барлық натурал сандар үшін орындалады (Aczel 1977:742).
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
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 1=n = 0 and proceeding onwards with 1=n = 1, 2, 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 is in \N. If an element n is in \N then n + 1 is in \N. \N is the smallest set 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. 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).
Рекурсивті анықтамалар нысаны
Көптеген рекурсивті анықтамалар екі негізге ие: негізгі жағдай (негіз) және индуктивті шарт. Дөңгелек анықтама мен рекурсивті анықтама арасындағы айырмашылық – рекурсивті анықтамада әрқашан негізгі жағдайлар болуы керек, олар өзінің анықтамасы арқылы емес, анықтаманы қанағаттандыратын жағдайлар, ал индуктивті шарттардағы барлық басқа жағдайлар қандай да бір мағынада "кішірек" болуы керек (яғни, рекурсияны тоқтататын негізгі жағдайларға жақын) – бұл "тек қарапайым жағдаймен рекурсия жасау" деп аталатын ереже. Керісінше, дөңгелек анықтамада негізгі жағдай болмауы мүмкін, тіпті функцияның мәні функцияның өзі арқылы, басқа мәндеріне емес, анықталуы мүмкін. Мұндай жағдай шексіз регреске алып келеді. Рекурсивті анықтамалардың жарамды екені – яғни, рекурсивті анықтама бірегей функцияны анықтайды – жиын теориясының рекурсия теоремасы деп аталатын теоремасы, оның дәлелі тривиальды емес. Егер функцияның домені натурал сандар болса, анықтаманың жарамды болуы үшін жеткілікті шарттар – f(0) мәнінің (яғни, негізгі жағдай) берілгендігі және n > 0 үшін f(n) мәнін n арқылы анықтауға арналған алгоритмнің берілгендігі (яғни, индуктивті шарт). Көбірек айтқанда, функциялардың рекурсивті анықтамасы домен жақсы реттелген жиын болған кезде трансфиниттік рекурсия принципін қолдану арқылы жасалуы мүмкін. Дұрыс рекурсивті анықтаманы құрайтын формальды критерийлер жалпы жағдайда күрделірек. Жалпы дәлелдеудің және критерийлердің сипаттамасын Джеймс Мункрестің «Топология» еңбегінде табуға болады. Дегенмен, жалпы рекурсивті анықтаманың нақты жағдайы (домен кез келген жақсы реттелген жиынның орнына оң бүтін сандармен шектелген) төменде берілген.
Рекурсивті анықтама принципі
A жиыны болсын, ал a0 A элементі болсын. Егер ρ функциясы оң бүтін сандардың бос емес кесіндісін A-ға бейнелейтін әрбір f функциясына A-ның бір элементін сәйкес келтірсе, онда бірегей функция бар, оның үшін: