استنادىء ذاتي

صيغة مرئية للاستنادىء الذاتي المعروف بإسم تأثير دروسته. السيدة في تلك الصورة تمسك بغرض يحتوي على صورة أصغر لها ممسكة بنفس الغرض، والتي بدورها تحتوي على صورة أصغر لها ممسكة بنفس الغرض، وهلم جرا.

استنادىء ذاتي بالإنگليزية: Recursion يعني تكرار الشيء، ويستخدم هذا المصطلح في الرياضيات وفي علوم الحاسوب ليعني تكرار التعريف للدالة نفسها. ويستخدم لتكرار الدالة مرة ثانية وإذا تمت عملية الاستنادىء الذاتي لمرة ثالثة يكرر نفس الشي. وعملية الاستنادىء الذاتي هي إستنادىء الشيء لنفسه. وفي البرمجة عندما تتم عملية الاستنادىء الذاتي للدالة أبجد فيتم كتابتها مرة ثانية إلى غير ذلك.

التعريفات الشكلية للاستنادىء الذاتي

Recursion in a screen recording program, where the smaller window contains a snapshot of the entire screen.

ونفس الأمر بالنسبة للبرمجة ففرضا لدينا الدالة Function التالية GetChile(ID)

هذا التابع يقوم بإرجاع جميع العناصر للعنصر الأب ذورقم التعريف ID وعندما يتم تطبيق التابع فإننا نبحث عن جميع أبناء العنصر المطلوب وعند إرجاع جميع عنصر ابن نطلب نفس التابع ولكن مع وضع رقم تعريف العنصر الابن وفي حال كان العنصر الأب لا يحوي عناصر أبناء لا نعيد شيء إلى غير ذلك حتى نستعيد شجرة بكل العناصر.

الاستنادىء الذاتي في اللغة

الاستنادىء الذاتي في الرياضيات

استنادىء ذاتي لمثلثات محصورة في مثلث سيرپنسكي لتشكل عقد هندسي.

فئات معرَّفة بالاستنادىء الذاتي

مثال: الأعداد الطبيعية

المثال القانوني للفئة الفهم بالاستنادىء الذاتي تعطيه الأعداد الطبيعية:

1 is in

{\displaystyle \mathbb {N

فلوn هي في

{\displaystyle \mathbb {N

، فإذن n + 1 is in

{\displaystyle \mathbb {N

The set of natural numbers is the smallest set satisfying the previous two properties.

مثال: فئة التقارير التي يمكن الوصول إليها بحق

Another interesting example is the set of all "true reachable" propositions in an axiomatic system.

الاستنادىء الذاتي في فهم الحاسب

This screenshot of a web page includes the screen shot itself.

مبرهنة الاستنادىء الذاتي

في نظرية الفئات، فهذه هي مبرهنة تضمن وجود الدوال الفهم باستخدام الدوال الفهم بالاستنادىء الذاتي. فلوافترضنا حتى لدينا X، وهوعنصر a في X والدالة ${\displaystyle f:X\rightarrow X$ ، المبرهنة تقول أنه هناك دالة فريدة ${\displaystyle F:\mathbb {N \rightarrow X$ (حيث ${\displaystyle \mathbb {N$ تشير إلى فئة الأعداد الطبيعية بما فيها صفر) بحيث

{\displaystyle F(0)=a

{\displaystyle F(n+1)=f(F(n))

لأي عدد طبيعي n.

برهان التفرد

Take two functions ${\displaystyle F:\mathbb {N \rightarrow X$ and ${\displaystyle G:\mathbb {N \rightarrow X$ بحيث:

{\displaystyle F(0)=a

{\displaystyle G(0)=a

{\displaystyle F(n+1)=f(F(n))

{\displaystyle G(n+1)=f(G(n))

حيث a هي عنصر في X.

ويمكن الاثبات باستخدام الاستقراء الرياضي حتى ${\displaystyle F(n)=G(n)$ لكل الأعداد الطبيعية n:

الحالة الأساسية:

{\displaystyle F(0)=a=G(0)

لذلك فالتساوي ساري لحالة

{\displaystyle n=0

.

Inductive Step: افترض

{\displaystyle F(k)=G(k)

لبعض

{\displaystyle k\in \mathbb {N

. Then

{\displaystyle F(k+1)=f(F(k))=f(G(k))=G(k+1).

Hence F(k) = G(k) implies F(k+1) = G(k+1).

By Induction, ${\displaystyle F(n)=G(n)$ for all ${\displaystyle n\in \mathbb {N$ .

أمثلة

بعض علاقات الاستنادىء الذاتي الشائعة هي:

Factorial: ${\displaystyle n!=n(n-1)!=n(n-1)\cdots 1$
Fibonacci numbers: ${\displaystyle f(n)=f(n-1)+f(n-2)$
Catalan numbers: ${\displaystyle C_{0 =1$ , ${\displaystyle C_{n+1 =(4n+2)C_{n /(n+2)$
Computing compound interest
The Tower of Hanoi
Ackermann function

انظر أيضاً

Church-Turing thesis
Continuous predicate
Corecursion
Course-of-values recursion
Fixed point combinator
Infinite loop
Infinitism
Iterated function
Mise en abyme
Primitive recursive function
Reentrant (subroutine)
Self-reference
Strange loop
Tail recursion
Turtles all the way down
Viable System Model

الهامش

وصلات خارجية

Johnsonbaugh, Richard (2004). Discrete Mathematics. Prentice Hall. ISBN .
Hofstadter, Douglas (1999). Gödel, Escher, Bach: an Eternal Golden Braid. Basic Books. ISBN .
Shoenfield, Joseph R. (2000). Recursion Theory. A K Peters Ltd. ISBN .
Causey, Robert L. (2001). Logic, Sets, and Recursion. Jones & Bartlett. ISBN .
Cori, Rene; Lascar, Daniel; Pelletier, Donald H. (2001). Recursion Theory, Godel's Theorems, Set Theory, Model Theory. Oxford University Press. ISBN .CS1 maint: multiple names: authors list (link)
Barwise, Jon; Moss, Lawrence S. (1996). Vicious Circles. Stanford Univ Center for the Study of Language and Information. ISBN .CS1 maint: multiple names: authors list (link) - offers a treatment of corecursion.
Rosen, Kenneth H. (2002). Discrete Mathematics and Its Applications. McGraw-Hill College. ISBN .
Cormen, Thomas H., Charles E. Leiserson, Ronald L. Rivest, Clifford Stein (2001). Introduction to Algorithms. Mit Pr. ISBN .CS1 maint: multiple names: authors list (link)
Kernighan, B.; Ritchie, D. (1988). The C programming Language. Prentice Hall. ISBN .CS1 maint: multiple names: authors list (link)
Stokey, Nancy,; Robert Lucas; Edward Prescott (1989). Recursive Methods in Economic Dynamics. Harvard University Press. ISBN .CS1 maint: multiple names: authors list (link)
Hungerford; title=Algebra (1980). Springer. ISBN . Missing pipe in: |author= (help); Missing or empty |title= (help), first chapter on set theory.
Recursion - tutorial by Alan Gauld
A Primer on Recursion- contains pointers to recursion in Formal Languages, Linguistics, Math and Computer Science
Zip Files All The Way Down
Nevins, Andrew and David Pesetsky and Cilene Rodrigues. Evidence and Argumentation: A Reply to Everett (2009). Language 85.3: 671--681 (2009)
Kaan, E. – Swaab, T. Y. (2002) “The brain circuitry of syntactic comprehension”, Trends in Cognitive Sciences, vol. 6, Issue 8, 350-356.