فى البداية اقرا المقال ده Recursion -- Part 1
احنا فى المرة الى فاتت اتعرضنا لموضوع الrecursionوعرفنا مع بعض يعنى ايه recursionوبنستخدمه امتى وليه وخدنا مثال عليه اللى هو الfactorial وعرفنا ان احنا ممكن نعمل البرنامج ب recursionوممكن من غيرها برضه.
وعرفنا برضه الrecursion بتتكون من ايه.
النهاردة ان شاء الله هنكمل مع بعض وناخد مثال تانى كدة نفهمه مع بعض ونشرحه بالتفصيل
قبل مانبدا لازم بس نكون عارفين شويه تعريفات كدة مهمه يعنى بخصوص موضوع ال recursion.
نبدا باول تعريــــــــــــــــــــــــــــــــــــــــــف......
- Direct Recursion:
A function is directly recursive if it contains an explicit call to itself.
يعنى ايه الكلام ده ؟ الى نفهمه من التعريف ده ان ال recursive funcion بتاعتنا نقدر نسميها direct لو هيا بتنده نفسها جوا الfuntion طيب تعالو ناخد مثال نفهم بيه احسن عندنا مثلا ال مثال ده ...
int foo(int x)
{
if (x <= 0)
return x;
else
return foo(x - 1);
}
هنا لاقينا ان الfunction بتاعتنا ندهت نفسها وهى جوه نفسها
تانى تعريف عندنا
- Indirect Recursion:
A function foo is indirectly recursive if it contains a call to another function which ultimately calls foo.
نقدر نقول على ال function الى عندنا انها Indirect Recursion لو لاقينا فى الfunction بتاعتنا جواها فى calling ل function تانية
int foo(int x)
{
if (x <= 0)
return x;
return bar(x);
}
int bar(int y)
{
return foo(y - 1);
}
هنا زى ماحنا شايفين فى ال 2 functions دول ان فى كل واحده جواها بتنادى على فانكشن تانيه
فى كمان تعريفين كدة انهردة نعرف بس اساميهم لكن مش هانخوض فيهم هانشرحهم ان شاء الله المرة الجايه وهما
- Tail Recursion
- Linear and Tree Recursion
طب تعالوا بقى ناخد مثال النهاردة ونفهمو مع بعض
المثال بتاع النهاردة حاجة اسمها Fibonacci seriesدى عبارة عن sequence بس ليها rule عشان نقدر نكونها يعنى مش اى ارقام وخلاص
عندنا فى ال sequence دى اول 10 ارقام منها هما دووول ومن خلالها نقدر نستنج القانون العام بتاعها
ال 10 ارقام اهم
0 1 1 2 3 5 8 13 21 34
الى انا ملونهم دول اول رقمين يعنى
fib[0] & fib[1]
ودول معروفين اساسا يعنى مش هانجيبهم لكن احنا هانبدا نجيب القانون عشان نجيب اللى بعد ال 1
طب اسيبكم كدة شويه تفكرو فى انكم تجيبو القانون من غير ماتبصو تحت لو مش عرفتوه بعد فترة ممكن تنزلة تبصوا عليه تحت انا كتبه يلا take your time
..........................
........................
......................
...................
...............
.........
.....
..
.
خلاص الوقت خلص نيجى بقى نفهم مع بعض
عندنا اول رقمين معروفين اللى هما 0 1 نيجى نركز شويه معلش استحملونى فى اللى بعد ال 1 نلاقيه 1 وبعد ال 1 نلاقيه 2 معنى كدة ايه....؟
خلاص انا هاقول مانا ادتكم فرصه فوق
معناها ان كل رقم = مجموع الرقمين الى قبليه يعنى عندنا اول رقمين 0 1 مجموعهم = 1
عندنا 1 1 مجموعهم 2 وهكذا .........اما نشوف مين الى فكر صح ؟؟ وجاب القانون من
غير مايبص تحت
طيب معنى كلامك ده ان ال
FIB -->Fibonacci
Fib(0) = 0
Fib(1) = 1
Fib(2) = Fib(1) + Fib(0) = 1
Fib(3) = Fib(2) + Fib(1) = 2
Fib(4) = Fib(3) + Fib(2) = 3
Fib(5) = Fib(4) + Fib(3) = 5
Fib(6) = Fib(5) + Fib(4) = 8
General rule:
Fib(n) = Fib(n-1) + Fib(n-2) for all n >=2
حاجة مهمة بقى
ممكن كل واحد قبل مايشوف الكود بتاع ال function دى يحاول يعمله هو بايده لو هو فهم المرة اللى فاتت واللى معرفش مش مشكله خالص يبص على الكود
int fib(int n) // n >= 0
{
if (n == 0)
return 0;
if (n == 1)
return 1;
return fib(n - 1) + fib(n - 2);
}
وده reference على النت