ملخص Recursion للمقابلات البرمجية

مقدمة

الـRecursion هي أسلوب لحل مسألة حسابية يعتمد فيه الحل على حلول نسخ أصغر من المسألة نفسها.

تحتوي جميع الدوال العودية على جزأين:

1. حالة أساس (أو حالات أساس) معرّفة تحدد متى تتوقف الـRecursion، وإلا فستستمر إلى الأبد!
2. تقسيم المسألة إلى مسائل فرعية أصغر واستدعاء الاستدعاء العودي

من أكثر أمثلة الـRecursion شيوعاً متتالية فيبوناتشي.

• حالتا الأساس: fib(0) = 0 وfib(1) = 1
• علاقة التكرار: fib(i) = fib(i-1) + fib(i-2)

def fib(n):
  if n <= 1:
    return n
  return fib(n - 1) + fib(n - 2)

تستخدم العديد من الـAlgorithms ذات الصلة بمقابلات البرمجة الـRecursion بكثافة، مثل الـBinary Search وترتيب الدمج واجتياز الـTrees وDFS وغيرها. في هذا المقال نركز على الأسئلة التي تستخدم الـRecursion وليست جزءاً من Algorithms أخرى معروفة.

مصادر التعلم

• قراءات
  • Recursion، University of Utah
• فيديوهات
  • Tail Recursion، University of Washington

أمور يجب الانتباه إليها أثناء المقابلات

• تذكر دائماً تعريف حالة أساس حتى تنتهي الـRecursion.
• الـRecursion مفيدة للتبديلات لأنها تولّد جميع التوافيق، وللأسئلة القائمة على الـTrees. يجب أن تعرف كيفية توليد جميع تبديلات متتالية وكذلك كيفية التعامل مع التكرارات.
• تستخدم الـcall stack ضمنياً. لذا يمكن إعادة كتابة جميع الأساليب الـRecursion بشكل تكراري باستخدام Stack. احذر الحالات التي يتعمق فيها مستوى الـRecursion كثيراً فيتسبب في طفح الـStack (الحد الافتراضي في Python هو 1000). قد تحصل على نقاط إضافية إذا أشرت إلى ذلك للمحاور. ولن تكون الـRecursion أبداً ذات تعقيد مساحي O(1) لأن Stack مشترك فيها، إلا إذا وُجد تحسين الاستدعاء الطرفي (TCO). اعرف ما إذا كانت لغتك المختارة تدعم TCO.
• عدد حالات الأساس — في مثال فيبوناتشي أعلاه، لاحظ أن أحد استدعاءاتنا الـRecursion يستدعي fib(n - 2). هذا يعني أنه يجب تعريف حالتي أساس حتى تغطي شيفرتك جميع الاستدعاءات الممكنة للدالة ضمن نطاق المدخلات. وإذا كانت دالتك الـRecursion تستدعي fn(n - 1) فقط، فحالة أساس واحدة تكفي.

الحالات الحدّية

• n = 0
• n = 1
• تأكد من أن لديك ما يكفي من حالات الأساس لتغطية جميع الاستدعاءات الممكنة للدالة الـRecursion

تقنيات

التذكير (Memoization)

في بعض الحالات، قد تحسب النتيجة لمدخلات سبق حسابها. لننظر إلى مثال فيبوناتشي مجدداً: fib(5) يستدعي fib(4) وfib(3)، وfib(4) يستدعي fib(3) وfib(2). يُستدعى fib(3) مرتين! إذا خُزّنت قيمة fib(3) وأعيد استخدامها، فإن ذلك يحسّن كفاءة الـAlgorithm كثيراً ويصبح الـtime complexity O(n).

أسئلة أساسية

هذه أسئلة أساسية للتدريب عليها إذا كنت تدرس هذا الموضوع.

• Generate Parentheses
• Combinations
• Subsets

أسئلة تدريب موصى بها

هذه أسئلة موصى بالتدريب عليها بعد أن تدرس الموضوع وتتدرب على الأسئلة الأساسية.

• Letter Combinations of a Phone Number
• Subsets II
• Permutations
• Sudoku Solver
• Strobogrammatic Number II (LeetCode Premium)

المصدر والرخصة

هذه الصفحة منسوخة من Tech Interview Handbook للمؤلف يانغشون تاي (Yangshun Tay)، النسخة المرجعية e1d28e8، وتُستخدم بموجب رخصة MIT — حقوق النشر (c) 2017-Present ليانغشون تاي. نص الرخصة محفوظ محلياً في /licenses/tech-interview-handbook.txt.