استنادىء ذاتي وتسمى كذلك التكرارية والعودية والتعاوديةوالمعاودة والارتدادية والاجترار هي عملية تكرار الشيء بطريقة مماثلة ذاتيا. على سبيل المثال، عندماقد يكون سطحا مرآتين متوازيين تماماً مع بعضها البعض الصور المتداخلة هي تعبير عن نوع من استنادىء ذاتي لانهائي. للمصطلح معانٍ متنوعة خاصة لمجموعة منوعة من المجالات من اللغويات إلى المنطق. الاستعمال الأكثر شيوعاً بالاستنادىء الذاتي هوفي الرياضيات وفهم الحاسوب، حيث أنه يشير إلى طريقة لتعريف دوال بحيث حتى الدالة الفهم تُستعمل في تعريف نفسها.

يجب حتى تمتلك دالة الاستنادىء الذاتي على خطوتين أساسيتين:

1- وجود شرط توقف معهد بشكل سليم مثل:

If (x<=1) return 1 

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

2- وجود خطوة الاستنادىء الذاتي التي يجب حتى تعهد بشكل سليم بحيث تؤدي إلى حالة توقف مثل:

(Return x*factorial(x-1

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

في الرياضيات وفهم الحاسوب، تظهر فئة من الكائنات أوالأساليب سلوك استنادىء ذاتي عندماقد يكون بالإمكان تعريفهم عن طريق خاصيتين:

• حالة أساس بسطية (أوعدة حالات)، و
• مجموعة من القواعد التي تقلص جميع الحالات الأخرى نحوحالة الأساس.

مثلا، التعريف بالاستنادىء الذاتي التالي هوتعريف لأسلاف شخص:

• والدا إنسان هم أسلافه (حالة الأساس)
• والدا أسلاف إنسان هم أيضا أسلافه (خطوة الاستنادىء الذاتي).

متتالية فيبوناتشي هي مثال تقليدي للاستنادىء الذاتي:

• (Fib(0 هو0 [حالة أساس]
• (Fib(1 هو1 [حالة أساس]
• لكل الأعداد السليمة n> 1:

(Fib(n هو((Fib(n-1) + Fib(n-2) [تعريف بالاستنادىء الذاتي]

الكثير من البديهيات مبنية على قواعد استنادىء ذاتي. مثلا، التعريف الرسمي للأعداد الطبيعية في نظرية المجموعات هو: 1 هوعدد طبيعي، ولكل عدد طبيعي عدد لاحق، والذي هوبحد ذاته عدد طبيعي. باستخدام حالة الأساس وقاعدة الاستنادىء الذاتي، بالإمكان إنتاج مجموعة جميع الأعداد الطبيعية.

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

كائنات فهم بالاستنادىء الذاتي تشتمل على الدوال، المجموعات وخاصة الكسيريات.

فكاهات الاستنادىء الذاتي

يتم استخدام الاستنادىء الذاتي بشكل فكاهي في فهم الحاسوب، البرمجة، الفلسفة، أوخط الرياضايات المدرسية; المثالان التاليان قد تكون تعريفات في القاموس:

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

راجع «استنادىء ذاتي».

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

إذا لم تزل تعهده، راجع «استنادىء ذاتي».

مثال آخر يوجد في فهرس في صفحة 269 في بعض نسخ كتاب كيرنيغان وريتشي «لغة البرمجة سي»; فإن الفهرس يشير باستنادىء ذاتي إلى نفسه:استعاء ذاتي 86. 139. 141. 182. 202. 269.

فكاهة مماثلة تظهر في النسخة الإنجليزية من محرك درس جوجل: عندما تبحث عن recursion، يقترح المسقط «هل تقصد: Recursion».

اختصارات الاستنادىء الذاتي تمكن حتى تكون نوع من الفكاهة في الاستنادىء الذاتي. بعض الأمثلة:

• بي إتش بي هي اختصار لـ "PHP Hypertext Preprocessor".
• WINE هي اختصار لـ "Wine Is Not an Emulator.
• GNU هي اختصار لـ "GNU's Not Unix"

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

المجموعات الفهم بالاستنادىء الذاتي

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

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

1 في ${\displaystyle \mathbb {N$

إذا كان n في ${\displaystyle \mathbb {N$، إذن n + 1 في ${\displaystyle \mathbb {N$

مجموعة الأعداد الطبيعية هي المجموعة الأصغر التي تحقق الخاصتين السابقين.

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

دالة قد تكون فهم جزئياً بنفسها. مثال مألوف هومتتالية فيبوناتشي: (F(n) = F(n − 1) + F(n − 2. ليكون التعريف مفيداً، يجب حتى يوصل إلى قيم غير فهم بالاستنادىء الذاتي، في هذه الحالة F(0) == 0 وF(1) == 1.

دالة اكرمن هي دالة استنادىء ذاتي مشهورة، والتي بخلاف متتالية فيبوناتشي، لا يمكن التعبير عنها بدون الاستنادىء الذاتي.

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

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

مثال تقليدي للاستنادىء الذاتي هوتعريف دالة العاملي، مثال بلغلة السي:

unsigned int factorial(unsigned int n) 
{
  if (n <= 1) 
    return 1;
  else
    return n * factorial(n-1);
 

تستدعي الدالة نفسها عودياً على نسخة أصغر من المدخل (n-1) وتضرب نتيجة الاستنادىء الذاتي بـ n، حتى تصل إلى حالة الأساس، بشكل مماثل للتعريف الرياضي للعاملي.

مثال تقليدي اخر بلغه السي بلس بلس:

#include <iostream>

using namespace std;

int main ()

{

long number;

cout << "Please type a number: ";

cin >> number;

cout << number << "! = " << factorial (number);

return 0;

في المثال السابق قمنا بكتابة إستنادىء ذاتى للدالة، أي الدالة قامت بمناداة نفسها من داخلها.

لاستخدام الاستنادىء الذاتي في خوارزمية إيجابيات وسلبيات. الميزة الرئيسية هي عادةً البساطة. الضرر الرئيسي هوغالباً حتى الخوارزمية قد تستلزم كمية كبيرة من الذاكرة إذا كان عمق الاستنادىء الذاتي كبير جداً.

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

في نظرية المجموعات، هذه مبرهنة التي تضمن وجود دوال فهم بالاستنادىء الذاتي. بإعطاء مجموعة 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.

برهان التميز

لتكن ${\displaystyle F:\mathbb {N \rightarrow X$ و${\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$.

خطوة الاستقراء: لنفرض حتى ${\displaystyle F(k)=G(k)$ لبعض ${\displaystyle k\in \mathbb {N$. إذن ${\displaystyle F(k+1)=f(F(k))=f(G(k))=G(k+1).$

ومن هنا F(k) = G(k) يؤدي إلى F(k+1) = G(k+1).

بالاسقراء , ${\displaystyle F(n)=G(n)$ لكل ${\displaystyle n\in \mathbb {N$.

أمثلة

بعض العلاقات العودية الشائعة:

وصلات خارجية

• 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.

مراجع