التفكير递归يًا
حالات الأساس والخطوات递归ية
التفكير递归يًا درس مجاني في Scala for Backend Engineering & Functional Programming على CoddyKit. هذا هو الدرس 1 من أصل 4. يمكنك قراءة الدرس كاملاً أدناه مجاناً — ثم تمرن عليه مباشرة في المتصفح باستخدام محرر أكواد مدمج ومدرس ذكاء اصطناعي متاح 24/7. هذا الدرس جزء من مسار التعلم في Scala for Backend Engineering & Functional Programming، وتقدمك يتزامن عبر الويب وتطبيق CoddyKit. تتضمن دورة Scala for Backend Engineering & Functional Programming 4 دروس في المجموع.
مفهوم الاستدعاء الذاتي
الاستدعاء الذاتي هو أن تستدعي الدالة نفسها لحل نسخة أصغر من المشكلة ذاتها.
في Scala، يلائم الاستدعاء الذاتي البرمجة الوظيفية طبيعيًا، لأنه يتيح لك التعبير عن الحلقات من دون متغيرات قابلة للتغيير.
تحتاج كل دالة ذات استدعاء ذاتي إلى أمرين: طريقة للتوقف، وطريقة لتصغير المشكلة.
حالة الأساس أولًا
حالة الأساس هي أبسط إدخال تستطيع الدالة الإجابة عنه مباشرة، من دون مزيد من الاستدعاء الذاتي.
من دون حالة أساس، ستستدعي الدالة نفسها إلى ما لا نهاية، ثم تتعطل بسبب تجاوز سعة المكدس.
صمّم حالة الأساس دائمًا قبل الخطوة التكرارية.
def countdown(n: Int): Unit =
if (n < 0) () // base case: stop
else {
println(n)
countdown(n - 1) // recursive step
}أول دالة ذات استدعاء ذاتي
إليك برنامجًا كاملًا يجمع الأعداد من 1 إلى n.
تعيد حالة الأساس القيمة 0؛ أما الحالة التكرارية فتضيف n إلى مجموع كل ما هو أصغر منه.
def sum(n: Int): Int =
if (n == 0) 0
else n + sum(n - 1)
@main def run(): Unit =
println(sum(5)) // 15تتبّع الاستدعاءات
لفهم الاستدعاء الذاتي، وسّع الاستدعاءات يدويًا.
يصبح sum(3) 3 + sum(2)، ثم يصبح 3 + 2 + sum(1)، ثم 3 + 2 + 1 + sum(0).
ولا تنهار السلسلة لتصبح قيمة واحدة، وهي 6، إلا بعد أن يعيد sum(0) القيمة 0.
// sum(3)
// = 3 + sum(2)
// = 3 + (2 + sum(1))
// = 3 + (2 + (1 + sum(0)))
// = 3 + (2 + (1 + 0))
// = 6الاستدعاء الذاتي مع القوائم
القوائم ذات طبيعة تكرارية: فالقائمة إما فارغة (Nil)، أو تتكون من رأس يتبعه ذيل أصغر.
ينطبق هذا الشكل مباشرة على الدوال ذات الاستدعاء الذاتي. فالقائمة الفارغة هي حالة الأساس، بينما يمثل الرأس مع الاستدعاء الذاتي على الذيل الخطوة التكرارية.
def length[A](xs: List[A]): Int = xs match {
case Nil => 0
case _ :: t => 1 + length(t)
}مطابقة نمط الذيل
يقسم النمط :: القائمة غير الفارغة إلى رأسها وذيلها.
يعمل كل استدعاء ذاتي على قائمة أقصر بصرامة، مما يضمن التقدم نحو Nil.
هذه هي الطريقة الاصطلاحية للتنقل في قائمة تكراريًا في Scala.
def sumList(xs: List[Int]): Int = xs match {
case Nil => 0
case h :: t => h + sumList(t)
}
@main def run(): Unit =
println(sumList(List(1, 2, 3, 4))) // 10استدعاءان ذاتيا
تتفرع بعض المسائل إلى أكثر من استدعاء ذاتي واحد.
المثال الكلاسيكي هو Fibonacci، حيث تعتمد كل قيمة على القيمتين السابقتين لها.
هذا الإصدار الساذج بسيط لكنه بطيء، لأنه يعيد حساب القيم نفسها مرات عديدة.
def fib(n: Int): Int =
if (n < 2) n
else fib(n - 1) + fib(n - 2)
@main def run(): Unit =
println(fib(7)) // 13تكلفة المكدس
يضيف كل استدعاء ذاتي إطارًا إلى مكدس الاستدعاءات، وعليه انتظار عودة الاستدعاء الداخلي.
في الاستدعاء الذاتي العميق جدًا، قد يستنفد ذلك سعة المكدس ويطرح StackOverflowError.
يساعدك حساب العمق، لا الحجم فقط، على توقّع هذا الخطر.
// This would overflow the stack for large n:
// def deep(n: Int): Int =
// if (n == 0) 0 else 1 + deep(n - 1)
// deep(1000000) // StackOverflowErrorالتقلص نحو حالة الأساس
الثابت الأساسي في الاستدعاء الذاتي هو أن كل استدعاء يجب أن يقترب من حالة الأساس.
إذا لم تصغر الوسيطة، أو لم تصل أبدًا إلى شرط التوقف، فلن ينتهي الاستدعاء الذاتي.
تحقق من ذلك قبل تشغيل أي شيء.
def reverse[A](xs: List[A]): List[A] = xs match {
case Nil => Nil
case h :: t => reverse(t) :+ h // t is smaller than xs
}الاستدعاء الذاتي مقابل الحلقات
يستخدم الأسلوب الإجرائي حلقات while مع عدادات قابلة للتغيير، بينما يستخدم الأسلوب الوظيفي الاستدعاء الذاتي مع قيم غير قابلة للتغيير.
يمكن لكليهما التعبير عن العمليات الحسابية نفسها، لكن الاستدعاء الذاتي يصف بنية البيانات بصورة أكثر مباشرة.
في Scala، ستفضل غالبًا الاستدعاء الذاتي أو الدوال ذات الترتيب الأعلى على الحلقات المباشرة.
// Imperative
var total = 0
for (i <- 1 to 5) total += i
// Recursive
def sum(n: Int): Int = if (n == 0) 0 else n + sum(n - 1)تصميم حل ذي استدعاء ذاتي
إليك منهجًا موثوقًا: حدّد حالة الأساس، وافترض أن الاستدعاء الذاتي يعمل بالفعل على الإدخال الأصغر، ثم ادمج الرأس مع النتيجة.
هذه القفزة الإيمانية هي جوهر التفكير بالاستدعاء الذاتي. فأنت تثق بالاستدعاء الأصغر ولا تتعامل إلا مع خطوة واحدة.
def maxOf(xs: List[Int]): Int = xs match {
case h :: Nil => h
case h :: t => math.max(h, maxOf(t))
}
@main def run(): Unit =
println(maxOf(List(3, 9, 2, 7))) // 9تحقق سريع
اختبر فهمك لبنية الاستدعاء الذاتي.
مراجعة
يحل الاستدعاء الذاتي المشكلة بتحويلها إلى نسخة أصغر من نفسها.
تحتاج كل دالة ذات استدعاء ذاتي إلى حالة أساس للتوقف، وإلى خطوة تكرارية تصغّر الإدخال باتجاه تلك الحالة.
تُعد القوائم، ببنيتها التي تتكون من Nil والرأس والذيل، بيئة مثالية للتفكير بالاستدعاء الذاتي. راقب عمق المكدس عند التعامل مع المدخلات الكبيرة جدًا.
الأسئلة الشائعة
هل درس «التفكير递归يًا» مجاني؟
نعم — نص درس «التفكير递归يًا» كامل متاح مجاناً هنا على الويب. لتمرينه بشكل تفاعلي (محرر أكواد مدمج ومدرس ذكاء اصطناعي متاح 24/7) وفتح باقي دورة Scala for Backend Engineering & Functional Programming، انتقل إلى CoddyKit PRO. تتضمن دورة Scala for Backend Engineering & Functional Programming 4 دروس في المجموع.
ماذا ستتعلم في «التفكير递归يًا»؟
حالات الأساس والخطوات递归ية تتمرن على Scala for Backend Engineering & Functional Programming مع أكواد عملية تشغلها مباشرة في المتصفح، ومدرس ذكاء اصطناعي متاح 24/7 يجيب على أسئلتك أثناء عملك.
هل أحتاج إلى خبرة سابقة لأبدأ Scala for Backend Engineering & Functional Programming؟
لا تُشترط خبرة سابقة. Scala for Backend Engineering & Functional Programming على CoddyKit منظم للمبتدئين حتى المتقدمين، لذا يمكنك البدء من هنا أو من البداية والتقدم بسرعتك الخاصة. هذا هو الدرس 1 من أصل 4.
كم من الوقت يستغرق درس «التفكير递归يًا»؟
معظم دروس CoddyKit تستغرق حوالي 5–10 دقائق. كل منها موجز وتفاعلي، لذا تحرز تقدماً مستمراً وتستأنف من حيث توقفت عبر الويب والتطبيق.
هل يمكنني كتابة وتشغيل أكواد في درس Scala for Backend Engineering & Functional Programming هذا؟
نعم. كل درس في Scala for Backend Engineering & Functional Programming يتضمن محرر أكواد مدمج، لذا تكتب وتشغل أكواداً حقيقية مباشرة في متصفحك وتحصل على تعليقات فورية من الذكاء الاصطناعي — بدون إعداد محلي.