Recursion

الاستدعـــاء الذاتي Recursion
غالباً ما نعرف مجموعة من الأشياء مرة واحدة فمثلا عناصر متتابعة أو عناصر مجموعة أو عمليات خوارزميه او برنامج ينفذ بناءاً على مدخلاته وأحيانا يكون التعريف لبعض الوحدات والعناصر بحيث يستدعي البرنامج نفسه أي يستدعي الصيغة السابقة له. فالاستدعاء الذاتي يعرف بأنه قابلية الخوارزمية أو البرنامج استدعاء نفسه وهو مفهوم رياضي وطريقة برمجية قيمه وأسلوب يمكن استخدامه بدل من التكرار.
مثال:
احتساب مفكوك دالة مفكوك (مضروب) العدد n
Factorial of n=n!
والذي يعرف رياضيا بالشكل التالي
n!={?(1 if n=0@n(n-1)! if n?0)?
0!=1 ,1!=1
على سبيل المثال لحساب
5!=5(5-1)!
=5(4)!
=5(4)(4-1)!
=5(4)(3)!
=5(4)(3)(3-1)!
=5(4)(3)(2)!
=5(4)(3)(2)(2-1)!
=5(4)(3)(2)(1)!
=5(4)(3)(2)(1)(1-1)!
=(5)(4)(3)(2)(1)
=120
The power function (x^m)
احتساب قيمة العدد (x ) مرفوع الى القوه m هي دالة معرفه بالشكل التالي
f(x^m )={?(1 if m=0@xf(x^(m-1) ) if m>0)?
Example:
Find 2^4
2^4=2(2^(4-1))
=2(2^3)
=(2)(2)(2^(3-1))
=(2)(2)(2^(2 ))
=(2)(2)(2)(2^(2-1))
=(2)(2)(2)(2^1)
=(2)(2)(2)(2)(2^(1-1))
=(2)(2)(2)(2)(2^0)
=(2)(2)(2)(2)(1)
=16
Ex (2): (Fibonacci sequence)
وهي متسلسلة من الاعداد كل عدد منها يساوي مجموع العددين اللذين يسبقانه فمثلا المتتابعة a_0,a_1,a_2,?,a_n
فأذا كان
a_0=0 or 1 or 1 or?
a_1=1 or 1 or 4 or ?
بداية من a_2 فان كل عدد يساوي مجموع العددين اللذان يسبقانه
أولاً: 0,1,1,2,3,5,8,13,?
ثانياً: 1,1,2,3,5,8,13,21 ,?
1,4,5,9,14,23,37,?

علاقات الاستدعاء الذاتي Recursion Relations
تعد علاقة الاستدعاء الذاتي واحدة من اهم المواضيع التي يمكن استخدامها في شتى المجالات كما هو الحال في أجهزة الاتصال التي تولد الاعداد العشوائية على شكل علاقات استدعاء ذاتي كما ان عدد الطرق التي يعيش بها الانسان الالي n من المرات والامتار على أساس كل خطوة هي متر أو متران . وكذلك فأن تكاثر الحيوانات كالأرانب وزيادة أعداد البشر جميعها يمكن تمثيلها على شكل علاقات استدعاء ذاتي.
تعريف :
اذا كانت a_0,a_1,a_2,?,a_n متتابعة فأن أي معادلة يكون أحد طرفيها الحد n بينما يكون الطرف الاخر بعض اوكل الحدود الذي سبقته مثل a_0,a_1,a_2,?,a_(n-1) تسمى علاقة استدعاء ذاتي
فمثلاً المتتابعتين
1,1,2,3,5,8,13,21,?
1,4,5,9,14,23,37,?
كل منها تحقق العلاقة
a_n=a_(n-1)+a_(n-2 )
أي ان علينا إعطاء متتابعة الحدين الاولين مع العلاقة وتسمى الحدود المعطاة بالشروط الابتدائية (initial condition)
?

حـل علاقـة الاستدعـاء الذاتي (solution of recursion relations)
أن حل علاقة الاستدعاء الذاتي للمتابعة a_0,a_1,a_2,?,a_n هي إيجاد صيغه صريحه للحد العام (وليس ضمنية) ونستخدم لذلك طرق المعاودة (التكرار) لحل علاقة الاستدعاء الذاتي فالحل يكون بإيجاد الحد العام a_n بدلالة بعض او كل الحدود السابقة له ثم الحد a_(n-1) بدلالة بعض او كل الحدود السابقة له وهكذا نستمر بالعملية لغاية الوصول الى الشروط الابتدائية وبذلك نحصل على متجه صريح للحد a_n .

Examples : solving the following recursion relation
? S?_n=2S_(n-1 ),S_0=1
Solution :
S_n=2S_(n-1 )
=2(2S_(n-2))
=(2)(2)S_(n-2)
= 2^2 S_(n-2)
=2^3 S_(n-3)
=2^4 S_(n-4)
=?
=2^n S_(n-n)=2^n S_0=2^n (1)=2^n

2)? C?_n=2C_(n-1)+1 ,C_1=1
=2(2C_(n-2)+1)+1
=2^2 C_(n-2)+2+1
=2^2 (?2C?_(n-3)+1)+2+1
=2^3 C_(n-3)+2^2+2+1
= ?
=2^(n-1) C_1+2^(n-2)+?+2^2+2+1
=2^(n-1)+2^(n-2)+?+2^2+2+1
=2^n-1
?_(r=1)^n?2^r =2+2^2+?+2^n=2(2^n-1)
1+2+?+2^(n-1)=2^n-1
ويمكن اثبات هذه العلاقة الصريحة باستخدام مبدأ الاستقراء الرياضي
نبرهن صحة القانون باستخدام مبدأ الاستقراء الرياضي عندما n=1
نفرض ان القانون صحيح عندما n=k
نبرهن صحة القانون عندما n=k+1
Note:
A linear recursion relation of the form ? a?_n=c_1 a_(n-1)+c_2 a_(n-2)+?c_k a_(n-k)
is called linear homogeneous recursion relation of order k .
تسمى علاقة استدعاء خطية متجانسة من الرتبة k .

Examples:
A_n=1.12 A_(n-1) ,A_0=1000
S_n=2 S_(n-1) ,S_0=1
C_n=2 C_(n-1)+1 ,C_1=1
f_n=f_(n-1) +f_(n-2) ,f_0=f_1=1
علاقة خطية متجانسة من الرتبة الاولى وبشرط ابتدائي A_0=1000 .
علاقة خطية متجانسة من الرتبة الاولى وبشرط ابتدائي S_0=1.
علاقة خطية متجانسة من الرتبة الاولى وبشرط ابتدائي C_1=1
علاقة خطية متجانسة من الرتبة الثانية وبشرط ابتدائي f_0=f_1=1 .
ملاحظة :
من الأساليب المألوفة لحل علاقات الاستدعاء الذاتي الخطية المتجانسة اف=تراض ان الحل يكون بالصيغة a_n=Ct^n ثم إيجاد قيم t وقيمة c التي تحقق الاستدعاء الذاتي .
Example:
Solve the following recursion relation with initial condition
A_n=1.12 A_(n-1) ,A_0= 1000
Solution:
Let A_n=Ct^n
? Ct^n=1.12 Ct^(n-1)
Ct^n-1.12 Ct^(n-1)=0
C(t^n-1.12t^(n-1) )=0 ,C?0
t^n-1.12t^(n-1)=0
? t?^(n-1) (t-1.12)=0
? t?^(n-1)?0
?t-1.12=0 ,t=1.12
? A_n=C(?1.12)?^n
? A?_0=C?(1.12)?^0
C=1000
? A_n=1000?(1.12)?^n