الاستدعاء الذاتي

التعريفات التراجعية

المضروب

مضروب العدد الطبيعي $n$ هو جداء الأعداد الطبيعية من 1 إلى $n$: $n! = 1 \cdot 2 \cdots n$، مع الاصطلاح $0! = 1$. والنقاط في هذه الصيغة تخفي حلقة، وقد علّم الدرس الحلقات كتابتها. غير أن التعريف نفسه يقبل صورة أخرى لا تذكر أي حلقة: مضروب $n$ يساوي $n$ مضروبًا في مضروب $n - 1$، ومضروب 0 يساوي 1.

هذا تعريف تراجعي: يعرّف مضروب $n$ بواسطة مضروب عدد أصغر. وليس دائريًا، لأن كل تطبيق للقاعدة الثانية ينزل درجة واحدة، والسلّم ينتهي عند الأولى: $3! = 3 \cdot 2! = 3 \cdot 2 \cdot 1! = 3 \cdot 2 \cdot 1 \cdot 0! = 6$. وللقاعدتين اسمان. الأولى هي الحالة الأساسية، التي تعطي النتيجة دون الإحالة إلى أي شيء آخر؛ والثانية هي الحالة التراجعية، التي تردّ المسألة إلى نسخة أصغر من المسألة نفسها.

تسمح C++ للدالة بأن تستدعي نفسها، وبذلك يُنقل التعريف حرفًا بحرف تقريبًا.

#include <print>​// مضروب n.// الشرط المسبق: 0 <= n <= 12 (يُعلَّل الحدّ لاحقًا).// الشرط اللاحق: تُعيد n! = 1 · 2 · ... · n، مع 0! = 1.int factorial(int n){    if (n == 0) {        return 1;                   // الحالة الأساسية    }    return n * factorial(n - 1);    // الحالة التراجعية}​int main(){    for (int n{0}; n <= 6; ++n) {        std::println("{}! = {}", n, factorial(n));    }}

0! = 11! = 12! = 23! = 64! = 245! = 1206! = 720

العقد ليس للزينة: مع $n = -1$ تستدعي الحالة التراجعية الدالة بـ $-2$، ثم بـ $-3$، ولا تبلغ 0 أبدًا؛ و$13!$ لا يتسع له int. كثير من النصوص التمهيدية تكتب هذا المضروب بالحالة الأساسية if (n == 0 || n == 1)، وهي زائدة لكنها غير ضارة، دون أن تقول شيئًا عن الأعداد السالبة ولا عن حجم النتيجة: فلا يتوقف كودها مع $n < 0$، ويعطي نتيجة لا معنى لها ابتداءً من $13!$. وسيُفحص كلا العيبين في القسم الخاص به.

الحالة الأساسية والحالة التراجعية

لكل دالة تراجعية حالة أساسية واحدة أو أكثر، تُحلّ مباشرة، وحالة تراجعية واحدة أو أكثر، تستدعي الدالة نفسها بقيمة ممرَّرة أصغر بمعنى دقيق ما، وتركّب ما تُعيده.

القوة $x^n$، حيث $n$ عدد طبيعي، تُعرَّف بـ $x^0 = 1$ و$x^n = x \cdot x^{n - 1}$: والحجم هنا هو الأس. ومجموع أرقام العدد الطبيعي $n$ (مجموع أرقام 2026 هو $2 + 0 + 2 + 6 = 10$) يُعرَّف هكذا: إذا كان $n < 10$، فالمجموع هو $n$، لأن له رقمًا واحدًا؛ وإلا فهو مجموع أرقام $\lfloor n / 10 \rfloor$، أي $n$ بلا رقمه الأخير، مضافًا إليه ذلك الرقم الأخير، $n \bmod 10$. والحجم هنا هو عدد الأرقام.

#include <print>​// x مرفوعًا إلى القوة n.// الشرط المسبق: n >= 0.// الشرط اللاحق: تُعيد x^n، مع x^0 = 1.double power(double x, int n){    if (n == 0) {        return 1.0;    }    return x * power(x, n - 1);}​// مجموع الأرقام العشرية لـ n.// الشرط المسبق: n >= 0.// الشرط اللاحق: تُعيد مجموع أرقام n.int digitSum(int n){    if (n < 10) {        return n;    }    return digitSum(n / 10) + n % 10;}​int main(){    std::println("2^10 = {}", power(2.0, 10));    std::println("1.5^3 = {}", power(1.5, 3));    std::println("مجموع أرقام 2026: {}", digitSum(2026));}

2^10 = 10241.5^3 = 3.375مجموع أرقام 2026: 10

فكتابة دالة تراجعية تقوم إذن على الإجابة عن سؤالين: أي الحالات تُحلّ بلا عون، وكيف يُحصل على حل حالة من حل حالة أصغر. فإذا كانت الإجابتان صحيحتين كانت الدالة صحيحة، والقسم الآتي يبرهن ذلك.