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

العودية أو الاستدعاء الذاتي في علم الحاسوب هو طريقة التي فيها الحل لمسألة ما يعتمد على حلول مسائل أصغر من نفس النوع.
بالإمكان تطبيق هذا النهج على أنواع عديدة من المسائل، وهو واحد من الأفكار المركزية بعلم الحاسوب.
تدعم أغلب لغات البرمجة الاستدعاء الذاتي عن طريق السماح لدالة أن تستدعي نفسها ضمن نص البرنامج نفسه. بعض لغات البرمجة الوظيفة لا تعرّف مبان تكرارية (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
تطبيق باستخدام جافا:
تطبيق باستخدام بايثون:
باستخدام جافاسكربت:
باستخدام ليسب:
باستخدام بيرل:
علاقة تكرارية للفيبوناتشي:
b$_n$ = b$_{n-1}$ + b$_{n-2}$
b$_1$ == 1, b$_0$ == 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

#### بحث ثنائي

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