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

[تصغير|300px|شجرة صنعت باستخدام [لوغو (لغة برمجة)|لغة لوجو وبالاعتماد بشكل كبير على الاستدعاء الذاتي.]]
**العودية** أو **الاستدعاء الذاتي** في علم الحاسوب هو طريقة التي فيها الحل لمسألة ما يعتمد على حلول مسائل أصغر من نفس النوع.

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

تدعم أغلب لغات البرمجة الاستدعاء الذاتي عن طريق السماح لدالة أن تستدعي نفسها ضمن نص البرنامج نفسه. بعض لغات البرمجة الوظيفة لا تعرّف مبان تكرارية (looping constructs) ولكن تعتمد فقط على الاستدعاء الذاتي لتكرار تنفيذ كود معين. برهنت نظرية الحاسوبية أن اللغات التي تستخدم الاستدعاء الذاتي فقط معادلة رياضياً للغات الحتمية، بمعنى أنه باستطاعتهم حل أي نوع من المسائل دون الحاجة لمباني التحكم النموذجية مثل حلقات "while" أو "for".

## برامج الاستدعاء الذاتي

### دوال الاستدعاء الذاتي
#### العاملي
مثال تقليدي لدالة الاستدعاء الذاتي هي دالة تستخدم لحساب العاملي لعدد صحيح:

: \operatorname{fact}(n) =
 \begin{cases}
 1 & \mbox{if } n = 0 \\
 n \cdot \operatorname{fact}(n-1) & \mbox{if } n > 0 \\
 \end{cases}


بالإمكان كتابة الدالة كعلاقة تكرارية:
:b_n = nb_{n-1}
:b_0 = 1

#### فيبوناتشي
دالة رياضية معروفة أخرى هي دالة التي تحسب أعداد فيبوناتشي:

 \operatorname{fib}(n) =
 \begin{cases}
 0 & \mbox{if } n = 0 \\
 1 & \mbox{if } n = 1 \\
 \operatorname{fib}(n-1) + \operatorname{fib}(n-2) & \mbox{if } n >= 2  \\
 \end{cases}


تطبيق باستخدام جافا:

```java
/**
     * 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);
	}
    }
```


تطبيق باستخدام بايثون:


```python
def fib(n):
    if n < 2:
        return n
    else:
        return fib(n-1) + fib(n-2)
```


باستخدام جافاسكربت:

```javascript
function fib (n) {
    if (!n) {
        return 0;
    } else if (n <= 2) {
        return 1;
    } else {
        return fib(n - 1) + fib(n - 2);
    }
}
```


باستخدام ليسب:

```lisp
(defun fib (n)
  (cond ((= n 0) 0)
        ((= n 1) 1)
        (t (+ (fib (- n 1))
              (fib (- n 2))))))
```


باستخدام بيرل:

```perl
sub fib {
    my ($n) = @_;
    ($n < 2) ? $n : fib($n - 2) + fib($n - 1);
}
```


علاقة تكرارية للفيبوناتشي:

bn = bn-1 + bn-2

b1 == 1, b0 == 0

#### قاسم مشترك أكبر

دالة استدعاء ذاتي أخرى مشهورة هي خوارزمية أقليدس، تستخدم لحساب القاسم المشترك الأكبر لعددين صحيحين:

: \gcd(x,y) =
 \begin{cases}
 x & \mbox{if } y = 0 \\
 \gcd(y, \operatorname{remainder}(x,y)) & \mbox{if } x \ge y \mbox{ and } y > 0 \\
 \end{cases}


علاقة تكرارية للقاسم المشترك الأكبر، بحيث أن x \% y يمثل الباقي من قسمة x / y:
:\gcd(x,y) = \gcd(y, x \% y)
:\gcd(x,0) = x

#### برج هانوي

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

: \operatorname{hanoi}(n) =
 \begin{cases}
 1 & \mbox{if } n = 1 \\
 2\cdot\operatorname{hanoi}(n-1) + 1 & \mbox{if } n > 1\\
 \end{cases}


علاقة تكرارية لبرج هانوي:
:h_n = 2h_{n-1}+1
:h_1 = 1

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

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

مثال لتطبيق البحث الثنائي باستخدام لغة سي:

```c
/*
  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);
 }
```


## انظر أيضًا
* استدعاء ذاتي
* برمجة وظيفية
* خوارزمية فرق تسد

## مراجع

تصنيف:تعبيرات اصطلاحية في البرمجة
تصنيف:عودية
تصنيف:الوظائف الفرعية
تصنيف:لغات برمجة وظيفية
تصنيف:علم الحاسوب النظري
تصنيف:نظرية الحسوبية