Recursionbase case · recursive case · call stack · recursion tree · memo

الـ function بتنادي نفسها on a smaller input، لحد ما توصل لـ input صغير قوي إجابته معروفة. دي المفتاح اللي هيفتح الـ trees والـ backtracking والـ DP، فهنبنيها من الصفر وعلى مهلنا.

قبله: Linked List و Stack بيمهّد لـ: Binary 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 ويعدّيها.

تشبيه السؤال «كام واحد قدّامك؟» هو الـ function، وكل واحد بيناديها على طابور أقصر بواحد. أول واحد هو الـ base case: إجابته معروفة from the start. من غيره السؤال هيفضل يتنقل لقدّام forever. وما حدّش عدّ الطابور كله، كل واحد عمل حاجة صغيرة قوي.

الطابور ده بالكود. i هو مكانك (index)، والـ function بترجّع عدد اللي قدّامك:

فوق الطابور، وتحت الـ call stack: كل صندوق نداء لسه ما خلصش.

بص على الحاجتين دول، لأنهم الفصل كله:

طب ما الـ loop أسهل هنا؟ آه. بنتعلم الشكل على مسائل سهلة الأول. بس لما الـ data نفسها مبنية من نسخ أصغر منها (linked list، tree، nested arrays، «طلّع كل الاحتمالات»)، الـ loop بتبقى كابوس والـ recursion بتبقى 5 سطور.

طب إزاي تعرف من كلام المسألة إن الحل recursive أصلًا؟ ده الجزء الجاي.

إزاي تعرف إن الحل recursion

السؤال اللي بيكشفها: «أقدر أوصف الحل باستخدام نفس المسألة على input أصغر؟». لو آه، فيه حل recursive. والكلمات دي بتقرّبك:

لما تشوف: tree / binary treelinked listnestedf(n) = … f(n - 1) all subsets / permutationsdivide in halfx to the power nsame structure inside itself
وخلي بالك لو: simple pass over an arrayn up to 10⁵ with one call per elementfib-like with no memo

آخر سطر مهم: لو العمق هيوصل n و n ممكن يبقى 100,000، الـ JS هيقع بـ RangeError لأن الـ stack ليه حد. هنشوف الحد ده بالأرقام في آخر الفصل.

النوعشكلهعدد النداءاتأمثلة
خطي
linear
نداء واحد، والـ input بيقل 1nfactorial، sum، Reverse String، Reverse Linked List
بالنص
halving
نداء واحد، والـ input بيتقسم على 2log nPower of Two، Pow(x, n)، binary search
شجرة
tree recursion
نداءين أو أكتر كل مرةممكن 2ⁿFibonacci، subsets، traversals الـ tree
على structure
on a list / tree
نداء على next أو على كل ابننداء لكل nodeMerge 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. يعني:

الجملتين دول بيتكتبوا كود حرفيًا:

  1. قبل أي سطر، قول الـ contract بجملة: factorial(n) بترجّع حاصل ضرب الأرقام من 1 لـ n. ده اللي هتعتمد عليه في السطر 3.
  2. الـ base case لازم ييجي قبل أي نداء. وليه <= مش === 1؟ عشان factorial(0): مع === 1 هتنادي -1 و -2 forever لحد الـ RangeError. امسك كل الحالات الصغيرة، مش رقم واحد بالظبط.
  3. نفس الـ function على n - 1: input أصغر وبيقرّب من الـ base case. والـ function بتقف هنا لحد ما النداء يرجع. حطينا النتيجة في smaller عشان الانتظار يبان، وفي العادي بتتكتب return n * factorial(n - 1).
  4. السطر ده بيتنفّذ on the way back up، بعد ما النداء يرجع. وكل نداء بيضرب الـ n بتاعه هو، لأن كل نداء ليه نسخة لوحده من المتغيرات.

التلات أسئلة اللي بتكتب بيهم أي recursive function

  1. إيه أصغر input أعرف إجابته على طول؟ ده الـ base case: 0، 1، array فاضية، null.
  2. إزاي أصغّر المسألة خطوة تقرّبني من الـ base case؟ n - 1، n / 2، i + 1، head.next.
  3. لو جالي حل المسألة الأصغر جاهز، أعمل بيه إيه؟ ده الـ combine: أضرب، أجمع، أوصّل pointer، أختار الأكبر.
من غير base case الـ function هتنادي نفسها لحد ما الـ stack يتملي، بعد حوالي 10 آلاف نداء، وتقع بـ 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 حالته:

التعقيد: 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 من غير ما تفكّر جواها إيه. شغلتك مستوى واحد بس:

  1. الـ base case صح؟ جرّبه بإيدك على أصغر input.
  2. النداء بيصغّر الـ input وبيقرّب من الـ base case؟
  3. لو النداء رجّع الإجابة الصح للجزء الأصغر، السطر بتاعي بيطلّع الإجابة الصح للـ 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 يتوصله وإجابته صح.

إمتى تتتبّع بإيدك؟ وإنت بتكتب: trust. وإنت بتعمل debug: اتتبّع على أصغر input (0، 1، 2) وارسم الـ frames على ورقة. أغلب الـ bugs بتبان في أول تلات مستويات.

كل اللي فات كان نداء واحد في كل مستوى. طب لو الـ 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). والتعريف بيتكتب كود حرفيًا:

  1. الـ contract: fib(n) بترجّع رقم Fibonacci رقم n، والعدّ من 0.
  2. base case بيمسك حالتين: return n صح لـ 0 و 1. ليه محتاجين الاتنين؟ لأن السطر 3 بيطرح 2. لو الـ base n === 1 بس، fib(2) هتنادي fib(0)، وهي هتنادي fib(-1) forever.
  3. نداءين. الـ 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
5159
1017719
2021,89139
302,692,53759
40331,160,28179

fib(40) بتعمل 331 مليون نداء، مع إن فيه بس 41 قيمة مختلفة من fib(0) لـ fib(40).

الـ memo في سطرين لو نفس النداء بيتكرر بنفس الـ input، احفظ إجابته أول مرة في Map، وبعد كده رجّعها من الـ Map من غير ما تنزل. كل 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:

  1. الـ LeetCode بيديك signature ثابتة زي sum(arr)، فبنعمل helper جوّاها (go أو dfs) هو اللي فيه الـ recursion. ولأنه جوّاها، بيشوف arr من غير ما نبعتها (closure).
  2. ليه i === arr.length مش arr.length - 1؟ الـ length معناه «عدّينا آخر عنصر، والباقي فاضي»، ومجموع الفاضي 0. فبيشتغل مع array فاضية. مع length - 1، الـ array الفاضية هتدوّر على i === -1 وعمرها ما هتلاقيه. خلّي الـ base «مفيش حاجة خالص».
  3. arr[i] + (trust) مجموع اللي بعده. مفيش نسخ، i + 1 رقم بس: O(n) time و O(n) stack.
  4. نبدأ من أول index. وخلي بالك من الـ return: من غيرها sum هترجّع undefined.
بديل للـ helper: default parameter function sum(arr, i = 0) وتنادي sum(arr, i + 1). الـ LeetCode بينادي sum(arr) فـ i بتبقى 0. أقصر، بس الـ helper أوضح لما تحتاج أكتر من parameter زي left و right.

ترجّع قيمة، ولا تجمّع في array برّا؟

الفخ: ترجّع arrays وتلزقها return [arr[i]].concat(go(i + 1)) كل مرة بتعمل array جديدة وتنسخ اللي راجع: نفس مشكلة الـ slice، O(n²). لو الإجابة list، اعمل collect.

كده معاك كل القطع. يلا نجمعها في template واحد هتكتب بيه أي recursion.

الـ template

  1. الـ contract الأول: «solve(input) بترجّع كذا». كل اللي جاي بيعتمد عليه.
  2. الـ base case قبل أي نداء. اسأل: كل input هيوصل هنا في الآخر؟ ولو فيه أكتر من حالة صغيرة (0 و 1، أو null و node واحدة)، امسكهم كلهم.
  3. smaller(input) لازم يكون أصغر فعلًا وبيقرّب من الـ base. وما تنساش تستخدم اللي راجع: نداء من غير ما تستخدم نتيجته غالبًا bug.
  4. الـ 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 فاضي. اللي يرجع من تحت هو نفسه الإجابة.

Power of Two

easyLeetCode 231

عندك رقم صحيح n (ممكن يكون سالب أو صفر). هل هو 2 مرفوعة لأس صحيح؟ يعني هل فيه k >= 0 يخلّي n = 2ᵏ؟

Input: n = 1 → true (2^0) Input: n = 32 → true (2^5) Input: n = 12 → false (12 → 6 → 3, and 3 is odd) Input: n = 0 → false

نفكّر فيها مع بعض

  1. افهم المطلوب: 1, 2, 4, 8, 16, …. كل واحد ضعف اللي قبله، فكل واحد غير الـ 1 زوجي، ولو قسمته على 2 يطلع power of two أصغر.
  2. الـ recursive case: 32 power of two لو وبس لو 16 كده. نفس السؤال على n / 2.
  3. الـ base cases: n === 1 يبقى true. فردي أكبر من 1 يبقى false. و n <= 0 false.
  4. بيصغر؟ كل نداء بيقسم على 2، يعني log₂ n نداء بالكتير.
  1. ليه أول سطر؟ عشان الصفر: 0 % 2 === 0 فهيعدّي من السطر 4، ويوصل لـ isPowerOfTwo(0 / 2)، نفس الـ input forever. recursive case ما بيصغّرش.
  2. الـ base اللي بيقول true. ليه 1 مش 2؟ لأن 1 = 2⁰. لو الـ base n === 2، الـ 1 هيوصل للسطر 4 ويطلع false غلط.
  3. base تاني بيقول false: أي فردي أكبر من 1 مستحيل. واستخدمنا !== 0 لأن في JS -3 % 2 بتطلع -1 مش 1.
  4. الـ return أهم كلمة هنا. النتيجة اللي جاية من تحت هي نفسها الإجابة. من غيرها الـ function هترمي النتيجة وترجّع undefined.

هنجرّب 32 (true)، وبعدين 12 (false). الـ true أو الـ false بتطلع لفوق من غير ما حد يلمسها:

Inputالمتوقعليه الحالة دي مهمة
0falseمن غير السطر 2، الصفر بيقسم نفسه forever
1true2⁰، الـ base case نفسه
-16falseالسالب عمره ما بيبقى 2ᵏ
6falseزوجي بس مش power: 6 → 3

التعقيد: O(log n) time و O(log n) stack. حتى 2³⁰ بيعمل 31 نداء بس.

في الانترفيو بعد الحل ده، اذكر الـ O(1) بالـ bits: n > 0 && (n & (n - 1)) === 0، لأن الـ power of two فيه bit واحدة بس مولّعة (Bit Manipulation).

هنا الإجابة كانت بتطلع لفوق. في المثال الجاي مفيش إجابة ترجع خالص: الـ function بتعدّل في الـ array نفسها.

مثال محلول 2: Reverse String

الجديد هنا حاجتين: helper بـ two indices، والشغل كله بيحصل قبل النداء. ومفيش ولا return value.

Reverse String

easyLeetCode 344

عندك array من الحروف. اعكسها in-place، في نفس الـ array من غير ما تعمل واحدة جديدة. الـ function ما بترجّعش حاجة.

Input: ["a","b","c","d","e","f"] → ["f","e","d","c","b","a"] Input: ["x","y","z"] → ["z","y","x"] Input: ["q"] → ["q"]

نفكّر فيها مع بعض

  1. بالـ loop: two pointers من الطرفين، swap وقرّب. ده اللي في Two Pointers، بـ O(1) memory.
  2. الشكل الـ recursive: بدّل أول وآخر حرف، واللي فاضل هو الحروف اللي جوه: نفس المسألة على جزء أصغر بحرفين.
  3. helper: محتاجين left و right، ومش هنعمل slice لأننا عايزين نعدّل الـ array الأصلية.
  4. الـ base case: لما مايفضلش حاجة. والفخ: لو الطول زوجي، الـ pointers بيعدّوا بعض ومش بيتقابلوا.
  1. ليه >= مش ===؟ في ["a","b","c","d"]: go(0, 3) ثم go(1, 2) ثم go(2, 1)، والـ 2 عمره ما هيساوي 1. مع === هيكمّل يبدّل لحد الـ RangeError. الـ >= بتمسك «اتقابلوا» و«عدّوا بعض»، وكمان الـ array الفاضية.
  2. swap بالـ destructuring: JS بيعمل array مؤقتة بالقيم القديمة الأول. لو كتبت s[left] = s[right]; s[right] = s[left]; القيمة الأصلية هتضيع.
  3. الـ left لقدّام والـ right لورا، فالمسافة بتقل 2 كل مرة. ومفيش ولا سطر بعد النداء، فلما يرجع الـ frame بيخلص على طول.
  4. 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.

Fibonacci Number

easyLeetCode 509

رجّع fib(n). عندك fib(0) = 0 و fib(1) = 1، وأي رقم بعد كده مجموع الاتنين اللي قبله. الـ n من 0 لـ 30.

Input: n = 5 → 5 (0, 1, 1, 2, 3, 5) Input: n = 7 → 13 Input: n = 0 → 0

نفكّر فيها مع بعض

  1. البديهي هو اللي في شجرة النداءات، وبيعدّي لأن n <= 30. بس أول سؤال في الانترفيو: «ولو n = 50؟».
  2. المشكلة: نفس الـ input بيتحسب كذا مرة. في fib(30)، الـ fib(3) لوحدها بتتحسب أكتر من 300 ألف مرة.
  3. الـ key insight: same input، same output، والـ function مش بتعدّل حاجة برّاها. فلو حسبناها مرة، نحفظها.
  4. الـ plan: Map من n للنتيجة. قبل أي حساب: «موجودة؟» رجّعها. مش موجودة؟ احسب، احفظ، رجّع.
  1. الـ default بيتحسب بس لما الـ parameter ما يتبعتش. الـ LeetCode بينادي fib(5) فبتتعمل Map مرة واحدة، وكل النداءات اللي جوه بتبعت نفس الـ Map.
  2. الـ base قبل الـ memo: 0 و 1 أسرع من السؤال في الـ Map.
  3. قلب الـ memo: early return من غير ولا نداء جديد، فكل الشجرة اللي كانت تحت النداء ده اتشالت. واستخدمنا has مش if (memo.get(n)) عشان قيمة 0 محفوظة كانت هتتحسب false.
  4. لازم تبعت memo في النداءين. من غيرها كل نداء هيعمل Map فاضية من الـ default، ونرجع لـ O(2ⁿ) من غير أي error.
  5. نحفظ قبل ما نرجّع، فأي نداء جاي لنفس الـ 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 بالظبط.

في الانترفيو قول التلات مراحل بالترتيب: البديهي O(2ⁿ) وليه (ارسم الشجرة)، بعدين الـ memo O(n)، بعدين الـ loop بـ O(1) memory. ده بيوري إنك فاهم، مش حافظ الحل الأخير.

الدرس من fib: ما تحسبش نفس الحاجة مرتين. المثال الجاي بيطبّق الدرس ده جوه نداء واحد، وبيقسم الـ input على 2 كمان.

مثال محلول 4: Pow(x, n) بالنص

الجديد هنا: النداء على نص الـ input، ونتيجته بتتستخدم مرتين من غير ما تتحسب مرتين. وكمان input سالب.

Pow(x, n)

mediumLeetCode 50

احسب x أُس n من غير Math.pow ولا **. الـ x عشري، والـ n صحيح ممكن يكون سالب ويوصل لـ -2³¹. الإجابة مقبولة لحد 5 أرقام بعد العلامة.

Input: x = 3, n = 4 → 81 Input: x = 2, n = -5 → 0.03125 (1 / 32) Input: x = 7, n = 0 → 1

نفكّر فيها مع بعض

  1. البديهي: اضرب x في نفسه n مرة: O(n)، ومع 2³¹ ده 2 مليار ضربة. وبالـ recursion (x * pow(x, n - 1)) هيقع بـ RangeError قبلها.
  2. الـ key insight: 2¹⁰ = 2⁵ × 2⁵. يعني xⁿ = (x^(n/2))² لو n زوجي، ولو فردي فاضل x واحدة: 2⁵ = 2² × 2² × 2.
  3. الفخ: لازم تنادي power(x, n/2) مرة واحدة وتحفظ النتيجة. نداءين على نفس الـ input هي نفس مشكلة fib، وهترجع O(n).
  4. السالب: x⁻⁵ = 1 / x⁵: احسب الموجب واقلبه.
  1. بنفصل السالب برّا، فـ power تشتغل على موجب بس. وفي n = -2³¹؟ الأرقام في JS doubles، فـ -n عادي. في C++ أو Java ده overflow لأن أكبر int هو 2³¹ - 1، فلازم long.
  2. الـ base الوحيد: أي حاجة أُس صفر بـ 1. والقسمة على 2 بتوصل لصفر من أي موجب: 1 → 0.
  3. أهم سطر: نداء واحد، والنتيجة في half. Math.floor لأن 5 / 2 = 2.5 في JS. وما تستخدمش n >> 1: الـ bit operators بتحوّل لـ 32-bit int، و 2147483648 >> 1 بتطلع رقم سالب.
  4. زوجي: 2¹⁰ = 2⁵ × 2⁵ = 32 × 32.
  5. فردي: Math.floor(5 / 2) = 2 و 2 + 2 = 4، ناقص واحد عن 5، فبنضرب x زيادة.

هنحسب myPow(2, -5): سالب، وفيه أُسس فردية وزوجية في السكة. النزول بيقسم والطلوع بيضرب:

Inputالمتوقعليه الحالة دي مهمة
x = 5, n = 01الـ base case على طول
x = 2, n = -30.125السالب: 1 / 8
x = -2, n = 3-8x سالب بيمشي عادي مع الضرب
x = 2, n = -21474836480power بتطلع Infinity، و 1 / Infinity = 0، وده المطلوب
x = 1.1, n = 21.21JS بيطلّع 1.2100000000000002، والـ judge بيقبله لحد 5 أرقام

التعقيد: O(log n) time و O(log n) stack. على 2³¹ هي 32 نداء بدل 2 مليار ضربة.

نفس الفكرة في حتت تانية اسمها fast power أو exponentiation by squaring، وهتقابلها في مسائل % 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.

Reverse Linked List

easyLeetCode 206

اعكس الـ linked list ورجّع الـ head الجديد. الحل بالـ loop وتلات pointers متشرح خطوة خطوة في فصل الـ Linked List، وهنا النسخة الـ recursive.

Input: 1 → 2 → 3 → 4 → 4 → 3 → 2 → 1 Input: null → null
  1. Base: list فاضية أو node واحدة: معكوسة أصلًا، رجّع head.
  2. أصغّر إزاي؟ الـ list من head.next.
  3. Combine: trust إن reverseList(head.next) عكست كل اللي بعدي. أنا لسه بشاور على head.next، اللي بقى آخر الجزء المعكوس. فأخلّيه يشاور عليّا، وأنا أشاور على null.
  1. حالتين: null للـ list الفاضية، و head.next === null لآخر node (هي دي الـ head الجديدة). والترتيب مهم: لو head بـ null وقرأت head.next الأول هتاخد TypeError، والـ || بيقف عند أول true.
  2. newHead هيبقى آخر node في الأصل، وبيعدّي لفوق زي ما هو.
  3. أصعب سطر. head.next لسه الـ node اللي بعدي، و .next = head معناها «شاور عليّا». اقراها على مرحلتين.
  4. بعد السطر 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.

Merge Two Sorted Lists

easyLeetCode 21

اتنين linked lists، كل واحدة مترتبة تصاعدي. ادمجهم في list واحدة مترتبة بنفس الـ nodes، ورجّع الـ head.

Input: l1 = 2 → 6 → 9, l2 = 1 → 6 → 7 → 10 Output: 1 → 2 → 6 → 6 → 7 → 9 → 10 Input: l1 = null, l2 = 0 → 0 Input: l1 = null, l2 = null → null

نفكّر فيها مع بعض

  1. بالـ loop و dummy node متشرحة في فصل الـ Linked List. هنا هنشوف قد إيه الـ recursion بتقصّرها.
  2. Base: لو list فيهم خلصت (null)، الدمج هو التانية زي ما هي، لأنها مترتبة أصلًا.
  3. أصغّر إزاي؟ أصغر node في الاتنين هو أول node في l1 أو l2. ده الـ head، واللي بعده = دمج الباقي.
  4. Combine: trust إن النداء هيرجّع الباقي مدموج، فوصّل بيه الـ node اللي كسبت (winner.next = …) ورجّعها.
  1. base لكل list. ولو الاتنين null، السطر 2 بيرجّع l2 اللي هو null، صح. ولازم قبل السطر 4، لأن null.val بتضرب TypeError.
  2. <= و < الاتنين صح هنا. الـ <= بتاخد من l1 عند التساوي، فالـ merge يبقى stable، وده هيفرق في الـ merge sort.
  3. النداء على l1.next مع l2 كلها، والنتيجة بتتحط في l1.next. الـ assignment بيحصل on the way back up، ورجوع l1 بيخلّي اللي فوق يوصّله.
  4. نفس الكلام لو l2 أصغر. ولو نسيت return في أي فرع، الـ .next اللي فوق هيبقى undefined والـ list تتقطع.

l1 = 2 → 5 → 7 (أزرق) و l2 = 2 → 3 → 8 (بنفسجي)، والـ nodes مترصّصة بالقيمة. في الأول الأسهم متلخبطة، وفي الآخر هتبقى خط واحد. الخضرا اتوصلت في الإجابة:

Inputالمتوقعليه الحالة دي مهمة
null, nullnullالسطر 2 بيرجّع l2 وهو null
5, 1 → 2 → 31 → 2 → 3 → 5l2 بتكسب 3 مرات ورا بعض وبعدين تخلص
1 → 1, 11 → 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 مهم.

Swap Nodes in Pairs

mediumLeetCode 24

بدّل كل اتنين nodes جنب بعض: الأولى مع التانية، والتالتة مع الرابعة، وهكذا. ممنوع تغيّر القيم، لازم تغيّر الـ pointers. ولو فاضل node لوحدها في الآخر تفضل مكانها.

Input: 1 → 2 → 3 → 4 → 5 → 2 → 1 → 4 → 3 → 5 Input: 7 → 8 → 8 → 7 Input: null → null

نفكّر فيها مع بعض

  1. Base: مفيش nodes أو node واحدة: مفيش زوج، رجّع head.
  2. أصغّر إزاي؟ أول زوج (first و second) بإيدنا، والباقي من second.next نفس المسألة على list أقصر بـ 2.
  3. Combine: first يشاور على الباقي المتبدّل، و second يشاور على first، و second هو الـ head الجديد للجزء ده.
  1. نفس base الـ reverse، وده اللي بيمسك الطول الفردي: آخر node بتوصل هنا لوحدها وترجع زي ما هي.
  2. أسماء ثابتة بدل head.next.next، لأن بعد أول تعديل في الـ pointers head.next هيشاور على حاجة تانية.
  3. النداء على second.next مش first.next، لأن first.next هو second نفسه. والنتيجة في first.next، لأن first هيبقى التاني في الزوج.
  4. نقلب الزوج. ده آمن دلوقتي لأن الباقي اتحفظ في first.next خلاص. ونرجّع second لأنه بقى أول الزوج.
Inputالمتوقعليه الحالة دي مهمة
nullnullالـ head === null في السطر 2
1 → 22 → 1زوج واحد، والنداء على null
1 → 2 → 32 → 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):

الحل: اعمل الـ stack بإيدك

الـ recursion في الحقيقة loop + stack بيديره الجهاز. تقدر تديره إنت بـ array عادية، ودي مالهاش حد الـ 10 آلاف. بدل ما تنادي، اعمل push للـ input، والـ loop تعمل pop لحد ما الـ stack يفضى. مثال الـ recursion طبيعية فيه: مجموع nested array زي [1, [2, [3, 4]], 5]:

  1. الـ stack فيه «الشغل اللي لسه ما اتعملش». في الأول الـ array كلها، زي أول نداء.
  2. مفيش return values، فبنجمع في متغير واحد برّا، نفس فكرة الـ collect في الـ helpers.
  3. pop بياخد آخر حاجة اتحطت (LIFO)، زي الـ call stack بالظبط.
  4. array؟ بدل ما ننادي على عناصرها، نحطها في الـ stack. ولأن الـ pop من الآخر، هتتعالج بالعكس. في الجمع مش فارقة، ولو الترتيب مهم (preorder في الـ trees) اعمل push بالعكس.
  5. رقم عادي: ده الـ base case، نجمعه ومفيش push.
الوصفة (1) اللي كان بيتغيّر من نداء للتاني هو اللي تعمله push (رقم، node، أو [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 + 1 frame مفتوحين مع بعض في أعمق نقطة
  • 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، فيه cycle
  • null

كل مستوى فوق بيصلّح الـ .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.

تمرين: فكّر قبل ما تفتح

Climbing Stairs

easyLeetCode 70

سلّم فيه n درجة، وكل مرة بتطلع درجة أو درجتين. بكام طريقة توصل لفوق؟ الـ n لحد 45.

n = 3 → 3 (1+1+1, 1+2, 2+1) n = 5 → 8
تلميح 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 دقيقة، ارجع للمثال المشابه هنا.

وآخر حاجة: الفصل كله في صفحة واحدة ترجعلها قبل أي انترفيو.

الخلاصة

في جملة واحدة حل أصغر حالة بإيدك (الـ base case)، وأي حالة تانية صغّرها خطوة وtrust إن الـ function هتحلها، وابني إجابتك على اللي راجع. والجهاز بيفتكر مكانك في كل مستوى بالـ call stack، اللي ليه تمن في الـ memory وليه حد.
السؤالالإجابة
الـ 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 نفسها.