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

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

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

تدعم أغلب لغات البرمجة الاستدعاء الذاتي عن طريق السماح لدالة أن تستدعي نفسها ضمن نص البرنامج نفسه. بعض لغات البرمجة الوظيفة لا تعرّف مبان تكرارية (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}}$

Pseudocode
function factorial is: input: integer n such that n >= 0 output: [n × (n-1) × (n-2) × … × 1] 1. if n is 0, return 1 2. otherwise, return [ n × factorial(n-1) ] end factorial

بالإمكان كتابة الدالة كعلاقة تكرارية:

$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}}$

Pseudocode
function fib is: input: integer n such that n >= 0 1. if n is 0, return 0 2. if n is 1, return 1 3. otherwise, return [ fib(n-1) + fib(n-2) ] end fib

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

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

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

b_n = b_n-1 + b_n-2

b₁ == 1, b₀ == 0

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

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

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

Pseudocode
function gcd is: input: integer x, integer y such that x >= y and y >= 0 1. if y is 0, return x 2. otherwise, return [ gcd(y, (remainder of x/y)) ] end gcd

علاقة تكرارية للقاسم المشترك الأكبر، بحيث أن $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$

Pseudocode
function hanoi is: input: integer n, such that n >= 1 1. if n is 1 then return 1 2. return [2 * [call hanoi(n-1)] + 1] end hanoi

بحث ثنائي

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

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

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

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

انظر أيضا

• استدعاء ذاتي
• برمجة وظيفية
• خوارزمية فرق تسد