Recursionbase case · recursive case · call stack · recursion tree · memo
الـ function بتنادي نفسها on a smaller input، لحد ما توصل لـ input صغير قوي إجابته معروفة. دي المفتاح اللي هيفتح الـ trees والـ backtracking والـ DP، فهنبنيها من الصفر وعلى مهلنا.
هتطلع من الفصل ده وإنت عارف
- تكتب أي recursive function من 3 أسئلة: الـ base case إيه، أصغّر المسألة إزاي، وأعمل إيه باللي راجع.
- تشوف الـ call stack في دماغك: frames بتنزل لتحت، وبعدين القيم بتطلع لفوق.
- تعرف ليه
fibالعادية O(2ⁿ) من شجرة النداءات، وإزاي الـ memo بينزّلها لـ O(n). - تمشي على array أو string بـ index مش بـ
slice، وتعرف إمتى ترجّع قيمة وإمتى تجمّع في array برّا. - تحل 7 مسائل كل واحدة بتزوّد فكرة، وتعرف حدود الـ stack في JS وإزاي تحوّل الـ recursion لـ loop.
يعني إيه recursion؟
في الفصل اللي فات شفنا إن الـ linked list هي node، وبعدها linked list أصغر. يعني الحاجة معرّفة بنسخة أصغر من نفسها. الفصل ده عن طريقة التفكير اللي بتمشي مع الشكل ده: recursion.
تخيّل إنك آخر واحد في طابور البنك، وعايز تعرف كام واحد قدّامك من غير ما تعدّ. تخبط على كتف اللي قدّامك: «كام واحد قدّامك؟». هو كمان مش عارف، فبيسأل اللي قدّامه نفس السؤال، وهكذا لحد أول واحد في الطابور. ده الوحيد اللي عارف من غير ما يسأل: «صفر». بعدين الإجابة بترجع لورا، وكل واحد بيزوّد 1 ويعدّيها.
الطابور ده بالكود. i هو مكانك (index)، والـ function بترجّع عدد اللي قدّامك:
فوق الطابور، وتحت الـ call stack: كل صندوق نداء لسه ما خلصش.
بص على الحاجتين دول، لأنهم الفصل كله:
- On the way down: كل نداء بيفتح نداء أصغر وبيستنّى. ما بيكمّلش السطر بتاعه لحد ما الإجابة ترجعله.
- On the way back up: من الـ base case الإجابات بترجع بالعكس، وكل نداء بيعمل عليها حاجة صغيرة (هنا
+ 1) ويعدّيها للي فوقه.
طب ما الـ loop أسهل هنا؟ آه. بنتعلم الشكل على مسائل سهلة الأول. بس لما الـ data نفسها مبنية من نسخ أصغر منها (linked list، tree، nested arrays، «طلّع كل الاحتمالات»)، الـ loop بتبقى كابوس والـ recursion بتبقى 5 سطور.
طب إزاي تعرف من كلام المسألة إن الحل recursive أصلًا؟ ده الجزء الجاي.
إزاي تعرف إن الحل recursion
السؤال اللي بيكشفها: «أقدر أوصف الحل باستخدام نفس المسألة على input أصغر؟». لو آه، فيه حل recursive. والكلمات دي بتقرّبك:
آخر سطر مهم: لو العمق هيوصل n و n ممكن يبقى 100,000، الـ JS هيقع بـ RangeError لأن الـ stack ليه حد. هنشوف الحد ده بالأرقام في آخر الفصل.
| النوع | شكله | عدد النداءات | أمثلة |
|---|---|---|---|
| خطي linear | نداء واحد، والـ input بيقل 1 | n | factorial، sum، Reverse String، Reverse Linked List |
| بالنص halving | نداء واحد، والـ input بيتقسم على 2 | log n | Power of Two، Pow(x, n)، binary search |
| شجرة tree recursion | نداءين أو أكتر كل مرة | ممكن 2ⁿ | Fibonacci، subsets، traversals الـ tree |
| على structure on a list / tree | نداء على next أو على كل ابن | نداء لكل node | Merge Two Lists، Swap Pairs |
flowchart TD
A["Answer = same problem on a smaller input?"] -- no --> L["Use a plain loop"]
A -- yes --> B{"Tree, nested data, or all combinations?"}
B -- yes --> R["Recursion is the natural fit"]
B -- no --> C{"Depth can reach 10^4 or more?"}
C -- yes --> S["Loop, or an explicit stack"]
C -- no --> R2["Recursion works; a loop may be simpler"]
الـ recursion مش دايمًا الإجابة، حتى لو المسألة شكلها recursive.
قبل أي مسألة، لازم تعرف الـ recursive function بتتكوّن من إيه. يلا نفصّص أبسط واحدة: factorial.
جسم أي recursive function: base case و recursive case
4! = 4 × 3 × 2 × 1 = 24. بس بص عليها كده: 4! = 4 × 3!، و 3! = 3 × 2!، لحد 1! = 1. يعني:
- Base case:
1! = 1، معروفة ومش محتاجة حساب. - Recursive case:
n! = n × (n - 1)!، الكبير معرّف بالأصغر منه بواحد.
الجملتين دول بيتكتبوا كود حرفيًا:
- قبل أي سطر، قول الـ contract بجملة:
factorial(n)بترجّع حاصل ضرب الأرقام من 1 لـ n. ده اللي هتعتمد عليه في السطر 3. - الـ base case لازم ييجي قبل أي نداء. وليه
<=مش=== 1؟ عشانfactorial(0): مع=== 1هتنادي-1و-2forever لحد الـRangeError. امسك كل الحالات الصغيرة، مش رقم واحد بالظبط. - نفس الـ function على
n - 1: input أصغر وبيقرّب من الـ base case. والـ function بتقف هنا لحد ما النداء يرجع. حطينا النتيجة فيsmallerعشان الانتظار يبان، وفي العادي بتتكتبreturn n * factorial(n - 1). - السطر ده بيتنفّذ on the way back up، بعد ما النداء يرجع. وكل نداء بيضرب الـ
nبتاعه هو، لأن كل نداء ليه نسخة لوحده من المتغيرات.
التلات أسئلة اللي بتكتب بيهم أي recursive function
- إيه أصغر input أعرف إجابته على طول؟ ده الـ base case: 0، 1، array فاضية،
null. - إزاي أصغّر المسألة خطوة تقرّبني من الـ base case؟
n - 1،n / 2،i + 1،head.next. - لو جالي حل المسألة الأصغر جاهز، أعمل بيه إيه؟ ده الـ combine: أضرب، أجمع، أوصّل pointer، أختار الأكبر.
RangeError: Maximum call stack size exceeded. أول ما تشوف الـ error ده اسأل: الـ base case موجود؟ والـ input فعلًا بيوصله؟
بس إزاي factorial(3) بتستنّى من غير ما الـ n بتاعها يتلخبط مع factorial(2)؟ ده شغل الـ call stack.
الـ call stack: إيه اللي بيحصل جوه الجهاز
كل نداء بيعمل frame: صندوق فيه متغيرات النداء ده (n و smaller)، و«أنا كنت واقف في أنهي سطر». الـ frames بتتحط فوق بعض في stack: آخر نداء اتفتح هو أول واحد يخلص. نفس الـ LIFO اللي شفته، بس الجهاز هو اللي بيديره.
factorial(4) سطر بسطر. الـ frame المتلوّن هو اللي شغال دلوقتي، وجنب كل frame حالته:
- في أعمق نقطة كان فيه 4 frames مفتوحين. يعني الـ recursion دي بتاخد memory بحجم
n، حتى من غير ولا array. ده اسمه stack space، وبيتحسب في الـ space complexity. - الضرب كله حصل on the way back up. وإحنا نازلين كنا بس بنفتح نداءات.
التعقيد: n نداء، كل واحد O(1)، يعني O(n) time و O(n) stack.
في factorial(4)، لما factorial(1) بترجّع 1، مين بيستلم الـ 1 ده؟
factorial(4)على طولfactorial(2)، لأنه الـ frame اللي تحته وهو اللي ناداه- الكود اللي نادى
factorial(4) - مفيش حد، الـ base case بيوقف البرنامج
كل نداء بيرجع للي ناداه، يعني الـ frame اللي تحته. factorial(2) بياخد الـ 1، يضربه في 2، ويرجّع 2. والـ base case ما بيوقفش البرنامج، بيوقف النزول بس.
تتبّع الـ frames بإيدك نافع في الـ debugging، بس مستحيل وإنت بتكتب الكود. طب تفكّر إزاي وإنت بتكتب؟
Trust the function: إزاي تفكّر وإنت بتكتب
أشهر غلطة: تحاول تمشي في دماغك على كل النداءات لحد تحت وإنت بتكتب. ده بيلخبط، ومع الـ trees هيبقى مستحيل.
الـ key insight: وإنت بتكتب سطر النداء، افترض إن الـ function شغالة صح على الـ input الأصغر، زي ما بتستخدم Math.max من غير ما تفكّر جواها إيه. شغلتك مستوى واحد بس:
- الـ base case صح؟ جرّبه بإيدك على أصغر input.
- النداء بيصغّر الـ input وبيقرّب من الـ base case؟
- لو النداء رجّع الإجابة الصح للجزء الأصغر، السطر بتاعي بيطلّع الإجابة الصح للـ input كله؟
لو التلاتة صح، الـ function صح لأي حجم. زي الدومينو: الأولى بتقع، وكل واحدة بتوقّع اللي بعدها، يبقى كلهم هيقعوا.
جرّبها على مسألة جديدة: مجموع الخانات
digitSum(1234) = 1 + 2 + 3 + 4 = 10. الـ base: رقم من خانة واحدة مجموعه هو نفسه. أصغّر: أشيل آخر خانة (1234 % 10 = 4 والباقي 123). الـ combine: trust إن digitSum(123) هترجّع 6، فالإجابة 4 + 6.
ليه Math.floor؟ لأن في JS 1234 / 10 = 123.4، مفيش integer division زي C++. من غيرها مش هتوصل لرقم صحيح أبدًا. ولو حطيت الـ base n === 0 بدل n < 10 هيشتغل برضه، بنداء زيادة. المهم إن الـ base يتوصله وإجابته صح.
كل اللي فات كان نداء واحد في كل مستوى. طب لو الـ function نادت نفسها مرتين؟
لما الـ function تنادي نفسها مرتين: شجرة النداءات
أرقام Fibonacci: 0, 1, 1, 2, 3, 5, 8, 13, …، كل رقم مجموع الاتنين اللي قبله. يعني fib(0) = 0 و fib(1) = 1، وبعد كده fib(n) = fib(n - 1) + fib(n - 2). والتعريف بيتكتب كود حرفيًا:
- الـ contract:
fib(n)بترجّع رقم Fibonacci رقمn، والعدّ من 0. - base case بيمسك حالتين:
return nصح لـ 0 و 1. ليه محتاجين الاتنين؟ لأن السطر 3 بيطرح 2. لو الـ basen === 1بس،fib(2)هتناديfib(0)، وهي هتناديfib(-1)forever. - نداءين. الـ JS بيقيّم الشمال الأول، فـ
fib(n - 1)بيخلص كله قبل ماfib(n - 2)يبدأ. وكل واحد بينادي اتنين، فالنداءات بتتفرّع زي الشجرة.
كل دايرة نداء: الابن الشمال fib(n - 1) واليمين fib(n - 2)، والرقم تحتها هو اللي رجّعته. الزرقا الفاتحة نداءات مفتوحة في الـ stack، والصفرا شغالة حالًا، والفيروزي خلص وكانت أول مرة نحسب القيمة دي. والحمرا بتحسب حاجة اتحسبت قبل كده بالظبط:
ليه ده O(2ⁿ)؟
عدّ الحمرا: أكتر من نص الشجرة شغل متعاد. ولو زوّدت n واحد، الشجرة الجديدة فيها القديمة كلها وكمان شجرة n - 2، يعني النداءات تقريبًا بتتضاعف. الشجرة عمقها n وكل مستوى بيتفرّع لاتنين، فالـ upper bound هو 2ⁿ. (الرقم الحقيقي حوالي 1.6ⁿ، بس O(2ⁿ) مقبولة في الانترفيو.)
| n | نداءات الحل البديهي | نداءات مع memo |
|---|---|---|
| 5 | 15 | 9 |
| 10 | 177 | 19 |
| 20 | 21,891 | 39 |
| 30 | 2,692,537 | 59 |
| 40 | 331,160,281 | 79 |
fib(40) بتعمل 331 مليون نداء، مع إن فيه بس 41 قيمة مختلفة من fib(0) لـ fib(40).
fib(k) بيتحسب once، فالنداءات تبقى حوالي 2n: من O(2ⁿ) لـ O(n). ده أول خطوة في الـ DP، والكود والـ animation في مثال Fibonacci.
كل الأمثلة لحد دلوقتي كانت على أرقام. طب لو الـ input array أو string؟ هنا فيه فخ performance مستخبي.
Recursion على array أو string: index مش slice
مجموع array بالـ recursion: «أول عنصر + مجموع الباقي». والباقي هو arr.slice(1):
صح، بس slice مش ببلاش: بتعمل array جديدة وتنسخ فيها n - 1 عنصر، وبعدها n - 2، وهكذا. المجموع حوالي n²/2 نسخة: O(n²) time. وكل النسخ دي عايشة مع بعض (كل frame ماسك نسخته)، فالـ memory كمان O(n²). ونفس الكلام على s.slice و s.substring.
الحل: سيب الـ array زي ما هي، وابعت index بيقول «أنا ابتديت من فين». النداء الأصغر هو نفس الـ array من i + 1:
- الـ LeetCode بيديك signature ثابتة زي
sum(arr)، فبنعمل helper جوّاها (goأوdfs) هو اللي فيه الـ recursion. ولأنه جوّاها، بيشوفarrمن غير ما نبعتها (closure). - ليه
i === arr.lengthمشarr.length - 1؟ الـlengthمعناه «عدّينا آخر عنصر، والباقي فاضي»، ومجموع الفاضي 0. فبيشتغل مع array فاضية. معlength - 1، الـ array الفاضية هتدوّر علىi === -1وعمرها ما هتلاقيه. خلّي الـ base «مفيش حاجة خالص». arr[i]+ (trust) مجموع اللي بعده. مفيش نسخ،i + 1رقم بس: O(n) time و O(n) stack.- نبدأ من أول index. وخلي بالك من الـ
return: من غيرهاsumهترجّعundefined.
function sum(arr, i = 0) وتنادي sum(arr, i + 1). الـ LeetCode بينادي sum(arr) فـ i بتبقى 0. أقصر، بس الـ helper أوضح لما تحتاج أكتر من parameter زي left و right.
ترجّع قيمة، ولا تجمّع في array برّا؟
- Return لما الإجابة رقم أو boolean أو node بتتبني من إجابات النداءات الأصغر: sum، count، max، height. الإجابة بتطلع لفوق وتتجمّع.
- Collect لما الإجابة «list بكل اللي لقيته»: كل المسارات، كل الـ subsets. كل نداء بيعمل push في
res. دي اللي هتستخدمها في الـ backtracking.
return [arr[i]].concat(go(i + 1)) كل مرة بتعمل array جديدة وتنسخ اللي راجع: نفس مشكلة الـ slice، O(n²). لو الإجابة list، اعمل collect.
كده معاك كل القطع. يلا نجمعها في template واحد هتكتب بيه أي recursion.
الـ template
- الـ contract الأول: «
solve(input)بترجّع كذا». كل اللي جاي بيعتمد عليه. - الـ base case قبل أي نداء. اسأل: كل input هيوصل هنا في الآخر؟ ولو فيه أكتر من حالة صغيرة (0 و 1، أو
nullو node واحدة)، امسكهم كلهم. smaller(input)لازم يكون أصغر فعلًا وبيقرّب من الـ base. وما تنساش تستخدم اللي راجع: نداء من غير ما تستخدم نتيجته غالبًا bug.- الـ combine بيحصل on the way back up. ساعات بيبقى فاضي، وساعات
return subبس. ده اللي بيفرّق الأمثلة عن بعض.
| الشغل بيحصل فين؟ | معناه | أمثلة في الفصل |
|---|---|---|
| ولا حاجة بعد النداء | الإجابة بتعدّي لفوق زي ما هي | Power of Two |
| قبل النداء (on the way down) | بتعمل شغلك وبعدين تبعت الباقي | Reverse String |
| بعد النداء (on the way back up) | بتستنى إجابة الباقي وتبني عليها | factorial، fib، Pow، Reverse Linked List، Merge، Swap |
يلا نطبّق. هنبدأ بأبسط شكل: نداء واحد، والإجابة بتطلع لفوق زي ما هي من غير أي combine.
مثال محلول 1: Power of Two
أول مثال أبسط شكل للـ template: نداء واحد، والـ combine فاضي. اللي يرجع من تحت هو نفسه الإجابة.
عندك رقم صحيح n (ممكن يكون سالب أو صفر). هل هو 2 مرفوعة لأس صحيح؟ يعني هل فيه k >= 0 يخلّي n = 2ᵏ؟
نفكّر فيها مع بعض
- افهم المطلوب:
1, 2, 4, 8, 16, …. كل واحد ضعف اللي قبله، فكل واحد غير الـ 1 زوجي، ولو قسمته على 2 يطلع power of two أصغر. - الـ recursive case:
32power of two لو وبس لو16كده. نفس السؤال علىn / 2. - الـ base cases:
n === 1يبقى true. فردي أكبر من 1 يبقى false. وn <= 0false. - بيصغر؟ كل نداء بيقسم على 2، يعني
log₂ nنداء بالكتير.
- ليه أول سطر؟ عشان الصفر:
0 % 2 === 0فهيعدّي من السطر 4، ويوصل لـisPowerOfTwo(0 / 2)، نفس الـ input forever. recursive case ما بيصغّرش. - الـ base اللي بيقول true. ليه 1 مش 2؟ لأن
1 = 2⁰. لو الـ basen === 2، الـ1هيوصل للسطر 4 ويطلع false غلط. - base تاني بيقول false: أي فردي أكبر من 1 مستحيل. واستخدمنا
!== 0لأن في JS-3 % 2بتطلع-1مش 1. - الـ
returnأهم كلمة هنا. النتيجة اللي جاية من تحت هي نفسها الإجابة. من غيرها الـ function هترمي النتيجة وترجّعundefined.
هنجرّب 32 (true)، وبعدين 12 (false). الـ true أو الـ false بتطلع لفوق من غير ما حد يلمسها:
| Input | المتوقع | ليه الحالة دي مهمة |
|---|---|---|
| 0 | false | من غير السطر 2، الصفر بيقسم نفسه forever |
| 1 | true | 2⁰، الـ base case نفسه |
| -16 | false | السالب عمره ما بيبقى 2ᵏ |
| 6 | false | زوجي بس مش power: 6 → 3 |
التعقيد: O(log n) time و O(log n) stack. حتى 2³⁰ بيعمل 31 نداء بس.
n > 0 && (n & (n - 1)) === 0، لأن الـ power of two فيه bit واحدة بس مولّعة (Bit Manipulation).
هنا الإجابة كانت بتطلع لفوق. في المثال الجاي مفيش إجابة ترجع خالص: الـ function بتعدّل في الـ array نفسها.
مثال محلول 2: Reverse String
الجديد هنا حاجتين: helper بـ two indices، والشغل كله بيحصل قبل النداء. ومفيش ولا return value.
عندك array من الحروف. اعكسها in-place، في نفس الـ array من غير ما تعمل واحدة جديدة. الـ function ما بترجّعش حاجة.
نفكّر فيها مع بعض
- بالـ loop: two pointers من الطرفين، swap وقرّب. ده اللي في Two Pointers، بـ O(1) memory.
- الشكل الـ recursive: بدّل أول وآخر حرف، واللي فاضل هو الحروف اللي جوه: نفس المسألة على جزء أصغر بحرفين.
- helper: محتاجين
leftوright، ومش هنعملsliceلأننا عايزين نعدّل الـ array الأصلية. - الـ base case: لما مايفضلش حاجة. والفخ: لو الطول زوجي، الـ pointers بيعدّوا بعض ومش بيتقابلوا.
- ليه
>=مش===؟ في["a","b","c","d"]:go(0, 3)ثمgo(1, 2)ثمgo(2, 1)، والـ 2 عمره ما هيساوي 1. مع===هيكمّل يبدّل لحد الـRangeError. الـ>=بتمسك «اتقابلوا» و«عدّوا بعض»، وكمان الـ array الفاضية. - swap بالـ destructuring: JS بيعمل array مؤقتة بالقيم القديمة الأول. لو كتبت
s[left] = s[right]; s[right] = s[left];القيمة الأصلية هتضيع. - الـ
leftلقدّام والـrightلورا، فالمسافة بتقل 2 كل مرة. ومفيش ولا سطر بعد النداء، فلما يرجع الـ frame بيخلص على طول. s.length - 1لأنه آخر index. لو كتبتs.lengthأول swap هيحطundefinedفي أول الـ array.
| Input | المتوقع | ليه الحالة دي مهمة |
|---|---|---|
| [] | [] | go(0, -1)، الـ >= بترجع على طول |
| ["q"] | ["q"] | go(0, 0) |
| ["a","b"] | ["b","a"] | أصغر طول زوجي: بعد swap واحد بيعدّوا بعض |
| ["x","y","z"] | ["z","y","x"] | طول فردي: الحرف اللي في النص مكانه |
التعقيد: n / 2 نداء، يعني O(n) time و O(n) stack. الـ loop بتعمل نفس الشغل بـ O(1)، فهي الأحسن هنا. إحنا بنتعلم الشكل اللي هتشوفه في الـ trees.
لحد هنا كل نداء بيفتح نداء واحد بس. المثال الجاي فيه نداءين، وهنشوف إزاي الـ memo بيلمّ الشجرة.
مثال محلول 3: Fibonacci Number، من البديهي للـ memo
الجديد هنا: نداءين في كل مستوى، ونفس الـ input بيتكرر، فبنحفظ الإجابات في memo.
رجّع fib(n). عندك fib(0) = 0 و fib(1) = 1، وأي رقم بعد كده مجموع الاتنين اللي قبله. الـ n من 0 لـ 30.
نفكّر فيها مع بعض
- البديهي هو اللي في شجرة النداءات، وبيعدّي لأن
n <= 30. بس أول سؤال في الانترفيو: «ولو n = 50؟». - المشكلة: نفس الـ input بيتحسب كذا مرة. في
fib(30)، الـfib(3)لوحدها بتتحسب أكتر من 300 ألف مرة. - الـ key insight: same input، same output، والـ function مش بتعدّل حاجة برّاها. فلو حسبناها مرة، نحفظها.
- الـ plan:
Mapمنnللنتيجة. قبل أي حساب: «موجودة؟» رجّعها. مش موجودة؟ احسب، احفظ، رجّع.
- الـ default بيتحسب بس لما الـ parameter ما يتبعتش. الـ LeetCode بينادي
fib(5)فبتتعمل Map مرة واحدة، وكل النداءات اللي جوه بتبعت نفس الـ Map. - الـ base قبل الـ memo: 0 و 1 أسرع من السؤال في الـ Map.
- قلب الـ memo: early return من غير ولا نداء جديد، فكل الشجرة اللي كانت تحت النداء ده اتشالت. واستخدمنا
hasمشif (memo.get(n))عشان قيمة0محفوظة كانت هتتحسب false. - لازم تبعت
memoفي النداءين. من غيرها كل نداء هيعمل Map فاضية من الـ default، ونرجع لـ O(2ⁿ) من غير أي error. - نحفظ قبل ما نرجّع، فأي نداء جاي لنفس الـ
nهيلاقيها في السطر 3.
نفس fib(5) بالـ memo. الدواير الخضرا لقت إجابتها في الـ Map ورجعت على طول. قارن حجم الشجرة باللي فوق:
9 نداءات بدل 15، وعلى n = 30 هي 59 بدل 2.7 مليون. كل fib(k) بيتحسب once، فـ O(n) time و O(n) memory. ولما تفهم ترتيب الحساب (من الصغير للكبير) تستغنى عن الـ recursion خالص، وده الـ DP:
ليه i <= n؟ كل لفة بتحسب fib(i)، وإحنا عايزين fib(n) نفسه. مع < هترجّع fib(n - 1)، نفس غلطة الـ FizzBuzz بالظبط.
الدرس من fib: ما تحسبش نفس الحاجة مرتين. المثال الجاي بيطبّق الدرس ده جوه نداء واحد، وبيقسم الـ input على 2 كمان.
مثال محلول 4: Pow(x, n) بالنص
الجديد هنا: النداء على نص الـ input، ونتيجته بتتستخدم مرتين من غير ما تتحسب مرتين. وكمان input سالب.
احسب x أُس n من غير Math.pow ولا **. الـ x عشري، والـ n صحيح ممكن يكون سالب ويوصل لـ -2³¹. الإجابة مقبولة لحد 5 أرقام بعد العلامة.
نفكّر فيها مع بعض
- البديهي: اضرب
xفي نفسهnمرة: O(n)، ومع2³¹ده 2 مليار ضربة. وبالـ recursion (x * pow(x, n - 1)) هيقع بـ RangeError قبلها. - الـ key insight:
2¹⁰ = 2⁵ × 2⁵. يعنيxⁿ = (x^(n/2))²لوnزوجي، ولو فردي فاضلxواحدة:2⁵ = 2² × 2² × 2. - الفخ: لازم تنادي
power(x, n/2)مرة واحدة وتحفظ النتيجة. نداءين على نفس الـ input هي نفس مشكلة fib، وهترجع O(n). - السالب:
x⁻⁵ = 1 / x⁵: احسب الموجب واقلبه.
- بنفصل السالب برّا، فـ
powerتشتغل على موجب بس. وفيn = -2³¹؟ الأرقام في JS doubles، فـ-nعادي. في C++ أو Java ده overflow لأن أكبر int هو2³¹ - 1، فلازمlong. - الـ base الوحيد: أي حاجة أُس صفر بـ 1. والقسمة على 2 بتوصل لصفر من أي موجب:
1 → 0. - أهم سطر: نداء واحد، والنتيجة في
half.Math.floorلأن5 / 2 = 2.5في JS. وما تستخدمشn >> 1: الـ bit operators بتحوّل لـ 32-bit int، و2147483648 >> 1بتطلع رقم سالب. - زوجي:
2¹⁰ = 2⁵ × 2⁵ = 32 × 32. - فردي:
Math.floor(5 / 2) = 2و2 + 2 = 4، ناقص واحد عن 5، فبنضربxزيادة.
هنحسب myPow(2, -5): سالب، وفيه أُسس فردية وزوجية في السكة. النزول بيقسم والطلوع بيضرب:
| Input | المتوقع | ليه الحالة دي مهمة |
|---|---|---|
| x = 5, n = 0 | 1 | الـ base case على طول |
| x = 2, n = -3 | 0.125 | السالب: 1 / 8 |
| x = -2, n = 3 | -8 | x سالب بيمشي عادي مع الضرب |
| x = 2, n = -2147483648 | 0 | power بتطلع Infinity، و 1 / Infinity = 0، وده المطلوب |
| x = 1.1, n = 2 | 1.21 | JS بيطلّع 1.2100000000000002، والـ judge بيقبله لحد 5 أرقام |
التعقيد: O(log n) time و O(log n) stack. على 2³¹ هي 32 نداء بدل 2 مليار ضربة.
% 1000000007 زي Count Good Numbers تحت. والقاعدة: لو بتنادي نفس الـ input مرتين، احفظه.
كفاية أرقام. الـ linked list من الفصل اللي فات مبنية recursive أصلًا، يلا نعكسها بالـ recursion.
مثال محلول 5: Reverse Linked List بالـ recursion
الجديد هنا: الـ input مش رقم، ده linked list. «الـ input الأصغر» هو الـ list من head.next، والـ combine بيغيّر pointers on the way back up.
اعكس الـ linked list ورجّع الـ head الجديد. الحل بالـ loop وتلات pointers متشرح خطوة خطوة في فصل الـ Linked List، وهنا النسخة الـ recursive.
- Base: list فاضية أو node واحدة: معكوسة أصلًا، رجّع
head. - أصغّر إزاي؟ الـ list من
head.next. - Combine: trust إن
reverseList(head.next)عكست كل اللي بعدي. أنا لسه بشاور علىhead.next، اللي بقى آخر الجزء المعكوس. فأخلّيه يشاور عليّا، وأنا أشاور علىnull.
- حالتين:
nullللـ list الفاضية، وhead.next === nullلآخر node (هي دي الـ head الجديدة). والترتيب مهم: لوheadبـnullوقرأتhead.nextالأول هتاخدTypeError، والـ||بيقف عند أول true. newHeadهيبقى آخر node في الأصل، وبيعدّي لفوق زي ما هو.- أصعب سطر.
head.nextلسه الـ node اللي بعدي، و.next = headمعناها «شاور عليّا». اقراها على مرحلتين. - بعد السطر 4 أنا بشاور عليه وهو بيشاور عليّا: cycle صغيرة. السطر ده بيكسرها. ومن غيره أول node في الأصل هتفضل بتشاور على التانية.
الـ nodes ثابتة مكانها والأسهم هي اللي بتتقلب. الأخضر اتعكس خلاص، والأصفر لسه متعكس حالًا:
التعقيد: O(n) time و O(n) stack. الـ loop بـ O(1) memory أحسن في الانترفيو، بس الـ recursive بيوري إنك فاهم «trust the function». حد LeetCode هنا 5000 node، فالـ stack مستحمل.
هنا كانت list واحدة. طب لو عندنا اتنين lists، وكل نداء لازم يختار ياخد من أنهي واحدة؟
مثال محلول 6: Merge Two Sorted Lists بالـ recursion
الجديد هنا: اتنين inputs، وكل نداء بيقرّر أنهي واحد فيهم اللي يصغر، فمحتاجين اتنين base cases.
اتنين linked lists، كل واحدة مترتبة تصاعدي. ادمجهم في list واحدة مترتبة بنفس الـ nodes، ورجّع الـ head.
نفكّر فيها مع بعض
- بالـ loop و dummy node متشرحة في فصل الـ Linked List. هنا هنشوف قد إيه الـ recursion بتقصّرها.
- Base: لو list فيهم خلصت (
null)، الدمج هو التانية زي ما هي، لأنها مترتبة أصلًا. - أصغّر إزاي؟ أصغر node في الاتنين هو أول node في
l1أوl2. ده الـ head، واللي بعده = دمج الباقي. - Combine: trust إن النداء هيرجّع الباقي مدموج، فوصّل بيه الـ node اللي كسبت (
winner.next = …) ورجّعها.
- base لكل list. ولو الاتنين
null، السطر 2 بيرجّعl2اللي هوnull، صح. ولازم قبل السطر 4، لأنnull.valبتضربTypeError. <=و<الاتنين صح هنا. الـ<=بتاخد منl1عند التساوي، فالـ merge يبقى stable، وده هيفرق في الـ merge sort.- النداء على
l1.nextمعl2كلها، والنتيجة بتتحط فيl1.next. الـ assignment بيحصل on the way back up، ورجوعl1بيخلّي اللي فوق يوصّله. - نفس الكلام لو
l2أصغر. ولو نسيتreturnفي أي فرع، الـ.nextاللي فوق هيبقىundefinedوالـ list تتقطع.
l1 = 2 → 5 → 7 (أزرق) و l2 = 2 → 3 → 8 (بنفسجي)، والـ nodes مترصّصة بالقيمة. في الأول الأسهم متلخبطة، وفي الآخر هتبقى خط واحد. الخضرا اتوصلت في الإجابة:
| Input | المتوقع | ليه الحالة دي مهمة |
|---|---|---|
| null, null | null | السطر 2 بيرجّع l2 وهو null |
| 5, 1 → 2 → 3 | 1 → 2 → 3 → 5 | l2 بتكسب 3 مرات ورا بعض وبعدين تخلص |
| 1 → 1, 1 | 1 → 1 → 1 | تساوي: الـ <= بتاخد من l1 الأول |
التعقيد: كل نداء بيشيل node، فـ O(n + m) time و O(n + m) stack. الـ loop والـ dummy نفس الوقت بـ O(1) memory، وهو الأمان لو الـ lists طويلة.
في الأمثلة اللي فاتت كل نداء بياكل node واحدة. في المثال الجاي كل نداء بياكل اتنين.
مثال محلول 7: Swap Nodes in Pairs
الجديد هنا: الخطوة بتشيل 2 nodes، فالـ base لازم يمسك الطول الفردي، وترتيب تعديل الـ pointers مهم.
بدّل كل اتنين nodes جنب بعض: الأولى مع التانية، والتالتة مع الرابعة، وهكذا. ممنوع تغيّر القيم، لازم تغيّر الـ pointers. ولو فاضل node لوحدها في الآخر تفضل مكانها.
نفكّر فيها مع بعض
- Base: مفيش nodes أو node واحدة: مفيش زوج، رجّع
head. - أصغّر إزاي؟ أول زوج (
firstوsecond) بإيدنا، والباقي منsecond.nextنفس المسألة على list أقصر بـ 2. - Combine:
firstيشاور على الباقي المتبدّل، وsecondيشاور علىfirst، وsecondهو الـ head الجديد للجزء ده.
- نفس base الـ reverse، وده اللي بيمسك الطول الفردي: آخر node بتوصل هنا لوحدها وترجع زي ما هي.
- أسماء ثابتة بدل
head.next.next، لأن بعد أول تعديل في الـ pointershead.nextهيشاور على حاجة تانية. - النداء على
second.nextمشfirst.next، لأنfirst.nextهوsecondنفسه. والنتيجة فيfirst.next، لأنfirstهيبقى التاني في الزوج. - نقلب الزوج. ده آمن دلوقتي لأن الباقي اتحفظ في
first.nextخلاص. ونرجّعsecondلأنه بقى أول الزوج.
| Input | المتوقع | ليه الحالة دي مهمة |
|---|---|---|
| null | null | الـ head === null في السطر 2 |
| 1 → 2 | 2 → 1 | زوج واحد، والنداء على null |
| 1 → 2 → 3 | 2 → 1 → 3 | طول فردي: الـ 3 بتفضل مكانها |
التعقيد: n / 2 نداء: O(n) time و O(n) stack. وفيه حل بالـ loop و dummy node بـ O(1) memory، تمرين حلو بعد فصل الـ Linked List.
كل الحلول دي عمقها n. طب لو n بقى 100,000؟
حدود الـ stack، وإزاي تحوّل الـ recursion لـ loop
الـ call stack مساحته ثابتة. في Node والـ browsers، function بسيطة بتوصل لحوالي 10 آلاف نداء متداخل وتقع (على Node طلع 9,778، والرقم بيختلف حسب الـ engine وحجم الـ frame):
- عمق
log n(Pow، binary search) دايمًا safe: 32 نداء لأي رقم. - عمق
nsafe بس لوnصغير.sumعلى10⁵عنصر هيقع. - في الـ trees العمق هو الـ height. tree متوازنة بمليون node عمقها 20، بس tree «مايلة» هي linked list وعمقها
n. - V8 ما بيعملش tail call optimization، فحتى لو النداء آخر حاجة في الـ function، الـ frame بيفضل.
الحل: اعمل الـ stack بإيدك
الـ recursion في الحقيقة loop + stack بيديره الجهاز. تقدر تديره إنت بـ array عادية، ودي مالهاش حد الـ 10 آلاف. بدل ما تنادي، اعمل push للـ input، والـ loop تعمل pop لحد ما الـ stack يفضى. مثال الـ recursion طبيعية فيه: مجموع nested array زي [1, [2, [3, 4]], 5]:
- الـ stack فيه «الشغل اللي لسه ما اتعملش». في الأول الـ array كلها، زي أول نداء.
- مفيش return values، فبنجمع في متغير واحد برّا، نفس فكرة الـ collect في الـ helpers.
popبياخد آخر حاجة اتحطت (LIFO)، زي الـ call stack بالظبط.- array؟ بدل ما ننادي على عناصرها، نحطها في الـ stack. ولأن الـ
popمن الآخر، هتتعالج بالعكس. في الجمع مش فارقة، ولو الترتيب مهم (preorder في الـ trees) اعمل push بالعكس. - رقم عادي: ده الـ base case، نجمعه ومفيش push.
[node, depth]). (2) الـ base case يبقى if جوه الـ loop من غير push. (3) النداءات تبقى push. هتستخدمها في الـ trees للـ preorder والـ inorder، وفي الـ DFS في الـ graphs.
شفت كام مكان سطر واحد غلط بيوقّع الـ recursion كلها؟ يلا نجمعهم في مكان واحد.
غلطات مشهورة
أغلب bugs الـ recursion واحد من اتنين: RangeError (ما وقفتش)، أو undefined (قيمة ضاعت في السكة). الغلطات دي ورا أغلبهم.
1. الـ base case موجود، بس الـ input مش بيوصله
الصح if (n <= 0) return;. لما الخطوة أكبر من 1، الـ base لازم يمسك range مش رقم واحد.
2. نسيت return قبل النداء
الـ true بترجع لـ frame واحد وتضيع. والـ undefined بيتحسب false في if، فالـ bug بيستخبى. لو الـ function بترجّع قيمة، كل فرع لازم يخلص بـ return.
3. الـ base case بعد النداء
الكود بيتنفّذ من فوق لتحت، فالشرط لازم ييجي قبل أي نداء.
4. slice أو substring في كل نداء
ابعت indices: go(left, right) ثم go(left + 1, right - 1)، زي Reverse String.
5. نفس النداء مرتين
كل مستوى بيفتح نداءين، فالشجرة بتتضاعف لحد 2^(log n) = n نداء. احفظ في half. لو شفت نفس النداء بنفس الـ arguments مرتين، يا متغير يا memo.
6. الـ memo ما اتبعتش في النداء
الإجابة صح، بس كل نداء شايف Map فاضية، فالحل O(2ⁿ) زي الأول. الـ bug ده ما بيبانش غير في الـ TLE.
دلوقتي جرّب نفسك: كام سؤال سريع، وتمرين تفكّر فيه قبل ما تفتح الحل.
اختبر نفسك
reverseString بالشرط if (left === right) return; بدل >=، على ["a","b","c","d"]. إيه اللي هيحصل؟
- هيشتغل صح عادي
- هيعكس نص الـ array بس
- الـ pointers هيعدّوا بعض من غير ما يتساووا، والـ recursion مش هتقف لحد
RangeError - هيطلع
TypeErrorفي أول نداء
go(0, 3) ثم go(1, 2) ثم go(2, 1): الطول زوجي فمفيش لحظة left === right. الـ >= بتمسك الحالتين.
إيه الـ space complexity بتاعة sum(arr) بالـ index (من غير slice)؟
- O(1)، لأننا ما عملناش أي array
- O(n)، لأن فيه
n + 1frame مفتوحين مع بعض في أعمق نقطة - O(log n)
- O(n²)
الـ call stack memory حقيقية: كل go(i) مستني go(i + 1). الـ O(n²) كانت للـ slice version.
في fib(10) بالـ memo، كام مرة fib(3) بتتحسب فعلًا (توصل للسطر اللي فيه النداءين)؟
- 21 مرة، زي الحل البديهي
- مرتين
- مرة واحدة، وأي نداء بعدها بيرجع من الـ Map
- ولا مرة، لأنها base case
أول مرة بتتحسب وتتحفظ، وبعد كده early return عند memo.has(n). (في البديهي بتتحسب 21 مرة فعلًا.)
في reverseList، شلنا السطر head.next = null. الـ list 1 → 2 → 3 هتطلع إيه؟
3 → 2 → 1عادي، السطر ده زيادة3 → 2 → 1 → nullبس أبطأ3 → 2 → 1 → 2 → 1 → …: الـ 1 لسه بيشاور على الـ 2، فيه cyclenull
كل مستوى فوق بيصلّح الـ .next بتاع اللي قبله، ماعدا أول node في الأصل: محدش بيلمس الـ next بتاعها غير السطر ده.
الـ time complexity لـ power لو كتبت power(x, n / 2) * power(x, n / 2) بدل half؟
- O(log n) زي ما هي
- O(n)
- O(n log n)
- O(2ⁿ)
العمق log n، بس النداءات بتتضاعف كل مستوى: 2^(log₂ n) = n. ومش O(2ⁿ) لأن العمق log n مش n.
تمرين: فكّر قبل ما تفتح
سلّم فيه n درجة، وكل مرة بتطلع درجة أو درجتين. بكام طريقة توصل لفوق؟ الـ n لحد 45.
تلميح 1
فكّر في آخر خطوة: وصلت لـ n يا من n - 1 يا من n - 2. يبقى ways(n) = ways(n - 1) + ways(n - 2). شكلها مألوف؟
تلميح 2
دي Fibonacci بـ base cases مختلفة: ways(1) = 1 و ways(2) = 2. ومع n = 45 البديهي هيعمل مليارات النداءات، فلازم memo.
الحل
ليه n <= 2 ترجّع n؟ درجة واحدة: طريقة واحدة. درجتين: طريقتين (1+1 أو 2). ولو الـ base n === 1 بس، هتحتاج تقرر ways(0) بكام. climbStairs(45) = 1836311903 بـ 87 نداء بس، ودي أول مسألة في فصل الـ DP.
لو الأسئلة دي عدّت معاك، روح على LeetCode بالترتيب اللي تحت.
اتمرن على LeetCode بالترتيب
حلّها كلها بالـ recursion حتى لو الـ loop أسهل، الهدف إن الشكل يبقى في إيدك. قبل ما تكتب، قول التلات أسئلة بصوت عالي. ولو قعدت أكتر من 25 دقيقة، ارجع للمثال المشابه هنا.
- Fibonacci Numberالبديهي الأول، وبعدين الـ memo. ارسم شجرة
fib(4)على ورقة. - Power of Tworecursion بالنص، والقيمة بتعدّي لفوق زي ما هي. ما تنساش الصفر.
- Power of Threeنفس الشكل بـ 3. لو كتبته في دقيقتين يبقى الـ template ثبت.
- Reverse Stringhelper بـ two indices، والشغل قبل النداء. اختبر طول زوجي.
- Reverse Linked Listالـ recursive والـ iterative. اشرح
head.next.next = headلنفسك. - Merge Two Sorted Listsاتنين base cases، والتوصيل on the way back up.
- Remove Linked List Elementsالجديد: نضّف الباقي الأول (
head.next = …)، وبعدين قرّر ترجّعheadولاhead.next. - Swap Nodes in Pairsأول medium: الخطوة بتشيل 2 nodes، والطول الفردي.
- Climbing Stairsfib متنكرة، ومن غير memo هتاخد TLE. باب الـ DP.
- Pow(x, n)نداء واحد على النص، والسالب، والـ
-2³¹. - K-th Symbol in Grammarrecursion على «الأب»: الحرف رقم k جاي من الصف اللي قبله عند
Math.ceil(k / 2). ما تبنيش الصفوف. - Count Good Numbersfast power مع
% 1000000007. الضرب بيعدّي2⁵³، فاستخدمBigInt.
وآخر حاجة: الفصل كله في صفحة واحدة ترجعلها قبل أي انترفيو.
الخلاصة
| السؤال | الإجابة |
|---|---|
| الـ base case يبقى إيه؟ | «مفيش حاجة خالص»: n <= 1، i === arr.length، left >= right، head === null. امسك range، مش رقم واحد. |
طلع RangeError؟ | الـ base مش بيتوصله، أو جاي بعد النداء، أو العمق فعلًا أكبر من 10 آلاف (loop أو explicit stack). |
الإجابة undefined؟ | فيه فرع مفيهوش return، غالبًا قدّام النداء. |
| الـ time complexity؟ | عدد النداءات × شغل كل نداء. خطي O(n)، بالنص O(log n)، نداءين من غير memo O(2ⁿ)، مع memo عدد الـ inputs المختلفة. |
| الـ space complexity؟ | أقصى عمق للـ stack: n، أو log n، أو الـ height في الـ trees. وزوّد الـ memo لو موجود. |
| Return ولا collect؟ | الإجابة رقم أو boolean أو node: return. الإجابة list حاجات: collect في res برّا. |
الفصل الجاي: Binary Trees. كل node ليها ابن شمال وابن يمين، وكل ابن tree كاملة. فأي مسألة tree هتبقى: base case (node === null)، ونداءين على left و right تعمل لهم trust، و combine. نفس شجرة نداءات fib، بس المرة دي الشجرة هي الـ data نفسها.