عودية (علم الحاسوب)

عودية (علم الحاسوب)
العودية أو الاستدعاء الذاتي في علم الحاسوب هو طريقة التي فيها الحل لمسألة ما يعتمد على حلول مسائل أصغر من نفس النوع.
بالإمكان تطبيق هذا النهج على أنواع عديدة من المسائل، وهو واحد من الأفكار المركزية بعلم الحاسوب.
تدعم أغلب لغات البرمجة الاستدعاء الذاتي عن طريق السماح لدالة أن تستدعي نفسها ضمن نص البرنامج نفسه. بعض لغات البرمجة الوظيفة لا تعرّف مبان تكرارية (looping constructs) ولكن تعتمد فقط على الاستدعاء الذاتي لتكرار تنفيذ كود معين. برهنت نظرية الحاسوبية أن اللغات التي تستخدم الاستدعاء الذاتي فقط معادلة رياضياً للغات الحتمية، بمعنى أنه باستطاعتهم حل أي نوع من المسائل دون الحاجة لمباني التحكم النموذجية مثل حلقات "while" أو "for".
برامج الاستدعاء الذاتي
دوال الاستدعاء الذاتي
العاملي
مثال تقليدي لدالة الاستدعاء الذاتي هي دالة تستخدم لحساب العاملي لعدد صحيح:
بالإمكان كتابة الدالة كعلاقة تكرارية:
فيبوناتشي
دالة رياضية معروفة أخرى هي دالة التي تحسب أعداد فيبوناتشي:
تطبيق باستخدام جافا:
/**
* Recursively calculate the kth Fibonacci number.
*
* @param k indicates which (positive) Fibonacci number to compute.
* @return the kth Fibonacci number.
*/
private static int fib(int k) {
// Base Cases:
// If k == 0 then fib(k) = 0.
// If k == 1 then fib(k) = 1.
if (k < 2) {
return k;
}
// Recursive Case:
// If k >= 2 then fib(k) = fib(k-1) + fib(k-2).
else {
return fib(k-1) + fib(k-2);
}
}
تطبيق باستخدام بايثون:
def fib(n):
if n < 2:
return n
else:
return fib(n-1) + fib(n-2)
باستخدام جافاسكربت:
function fib (n) {
if (!n) {
return 0;
} else if (n <= 2) {
return 1;
} else {
return fib(n - 1) + fib(n - 2);
}
}
باستخدام ليسب:
(defun fib (n)
(cond ((= n 0) 0)
((= n 1) 1)
(t (+ (fib (- n 1))
(fib (- n 2))))))
باستخدام بيرل:
sub fib {
my ($n) = @_;
($n < 2) ? $n : fib($n - 2) + fib($n - 1);
}
علاقة تكرارية للفيبوناتشي:
bn = bn-1 + bn-2
b1 == 1, b0 == 0
قاسم مشترك أكبر
دالة استدعاء ذاتي أخرى مشهورة هي خوارزمية أقليدس، تستخدم لحساب القاسم المشترك الأكبر لعددين صحيحين:
علاقة تكرارية للقاسم المشترك الأكبر، بحيث أن يمثل الباقي من قسمة :
برج هانوي
للنقاش الكامل وشرح المسألة، راجع المقال التفصيلي. ببساطة احسب المسألة هكذا: بإعطاء ثلاثة أعمدة، واحد مع مجموعة من N أقراص بحجم متزايد، حدد العدد الأصغر من الخطوات لنقل جميع الأقراص من مكانهم البدائي إلى عمود آخر بدون وضع قرص ما فوق قرص أصغر منه.
علاقة تكرارية لبرج هانوي:
بحث ثنائي
خوارزمية البحث الثنائي هي طريقة للبحث في مصفوفة مرتبة عن عنصر واحد عن طريق تقسيم المصفوفة للنصف في كل مرور. الخدعة هي اختيار نقطة وسطية قريبة عن مركز المصفوفة، قارن القيمة في النقطة مع القيم المراد البحث عنها ومن ثم اتباع واحد من ثلاث الخيارات التالية: القيمة وجدت في النفطة الوسطية، قيمة النقطة الوسطية أكبر من القيمة المراد البحث عنها، أو أن قيمة النقطة الوسطية أصغير من القيمة المراد البحث عنها.
يتم استخدام الاستدعاء الذاتي لأن بكل مرور يتم إنشاء مصفوفة جديدة عن طريق تقسيم القديمة للنصف. ويتم استدعاء دالة البحث ذاتياً، هذه المرة على مصفوفة جديدة (وأصغر).
مثال لتطبيق البحث الثنائي باستخدام لغة سي:
/*
Call binary_search with proper initial conditions.
INPUT:
data is an array of integers SORTED in ASCENDING order,
toFind is the integer to search for,
count is the total number of elements in the array
OUTPUT:
result of binary_search
*/
int search(int *data, int toFind, int count)
{
// Start = 0 (beginning index)
// End = count - 1 (top index)
return binary_search(data, toFind, 0, count-1);
}
/*
Binary Search Algorithm.
INPUT:
data is a array of integers SORTED in ASCENDING order,
toFind is the integer to search for,
start is the minimum array index,
end is the maximum array index
OUTPUT:
position of the integer toFind within array data,
-1 if not found
*/
int binary_search(int *data, int toFind, int start, int end)
{
//Get the midpoint.
int mid = start + (end - start)/2; //Integer division
//Stop condition.
if (start > end)
return -1;
else if (data[mid] == toFind) //Found?
return mid;
else if (data[mid] > toFind) //Data is greater than toFind, search lower half
return binary_search(data, toFind, start, mid-1);
else //Data is less than toFind, search upper half
return binary_search(data, toFind, mid+1, end);
}
انظر أيضا
استدعاء ذاتي
برمجة وظيفية
خوارزمية فرق تسد
مراجع
استدعاء ذاتي
الوظائف الفرعية
لغات برمجة وظيفية
معلوماتية نظرية
نظرية قابلية الحساب