الدورة
العودية والتراجع دورة برمجة متوسطة المستوى من سبعة دروس، بعد دورة Python من الصفر ودورة أصلح الخطأ. معظمها يعمل على بنية Pi ذات LEDين في المعرض (الأحمر على GPIO17 والأصفر على GPIO27)، وتستخدم المهمة النهائية وحدة إشارة المرور. كل خطوة تُفحص مقابل ما يطبعه Pi أو ما تفعله أطرافه، وكل رقم في الدروس هو رقم يطبعه البرنامج فعلاً.
- نداءات تنادي نفسها: عد تنازلي بلا حلقة، رصة النداءات مرسومة كإزاحات أثناء النزول والصعود، مضروب بأعداد صحيحة كبيرة دقيقة (25! كاملاً)، مثلث Sierpinski مطبوع كنص، وLED يومض خمس مرات بالعودية.
- الحالات الأساسية: غوص في كهف بلا قاع يفيض فوق الرصة، حالة أساسية توقفه، حد العمق المُقاس (أقل قليلاً من 1,000 نداء لدالة صغيرة)، رفع القوة بالتربيع (2^100 في 8 نداءات)، ولماذا يُفضّل عمل الخط المستقيم في حلقة.
- Tree walks: a cave of tunnels stored as nested tuples, printed as an outline, its 9 rooms counted, its deepest point found, a route to the glow worm grotto by depth-first search, then the Pi's own folders walked with the same pattern.
- التبديلات: كل ترتيب لطاقم، n! معدود حتى 720، إشارة فضائية مشوشة تُفك شيفرتها مقابل مجموعة كلمات، أحمال الروفر تُحزم بنمط «خذ أو اترك»، والنتيجة تُفحص مقابل
itertools.permutations. - التراجع: ملكات N باختر واستكشف وألغِ الاختيار؛ كل الحلول معدودة من 4 إلى 8 (92 لرقعة الشطرنج)؛ 15,720 مربعاً مفحوصاً بدل 16 مليون رقعة؛ LED الأصفر يومض عند كل تراجع؛ ومتاهة كهف بحري يُهرب منها.
- التخزين المؤقت (Memoization): 21,891 نداءً لفيبوناتشي الساذج لحساب fib(20)، وقاموس يخفضها إلى 39، و
functools.lru_cacheمع عدّاد إصاباته وأخطائه، و601,080,390 مساراً للروفر عبر شبكة، و242 طريقة لتكوين دولار. - المهمة النهائية: حلال Sudoku: الختام.
الخاتمة
تبني المهمة النهائية حلال Sudoku كاملاً في نحو عشرين سطراً. يحمّل لغزاً حقيقياً، يكتب القواعد كدالة ويجرّبها على خانة واحدة، ثم يحل الرقعة بالتراجع: اعثر على أول خانة فارغة، جرّب كل رقم يناسبها، حل الباقي، وأعد الرقم إذا فشل ذلك. فحص مستقل يثبت أن كل صف وعمود ومربع يحتوي 1 إلى 9 (4,208 وضعاً لهذا اللغز)، إشارات المرور تظهر أصفر أثناء التفكير وأخضر عند الحل، وحاجز يحوّل الضوء أحمراً للغز يخالف القواعد قبل أن يهدر الحلال عليه لحظة.
ما يفعله محرك Pi بشكل مختلف
يعمل Pi بـ MicroPython 1.29 وليس CPython، والعودية هي حيث يظهر ذلك أكثر:
- العودية العميقة جداً ترفع
RuntimeError: maximum recursion depth exceeded، أوRuntimeError: pystack exhaustedلدالة كثيرة المتغيرات المحلية. أماRecursionError، اسم CPython، فغير معرّف هنا. الدروس تلتقطRuntimeError، الذي يعمل على كليهما، لأنRecursionErrorفي CPython نوع منRuntimeError. - الحد هو ذاكرة الرصة، لا عدداً ثابتاً: نحو 980 نداءً لدالة صغيرة، وأقل لدالة أكبر. لا يوجد
sys.setrecursionlimit. - القواميس لا تحفظ ترتيب إدخال المفاتيح، لذا تُخزّن الأشجار كقوائم ومجموعات (tuples)، ويُرتّب
os.listdirوالمجموعات قبل الطباعة. str.ljustوstr.rjustغير متوفرتين، لذلك يُبنى الحشو باستخدام" " * count. لا يوجد حد لحجم الأعداد الصحيحة، كما في CPython.
كل ما تبقى في الدورة، functools.lru_cache وitertools وos، يعمل كما على Pi حقيقية.