العودية
تحتاج هذه الصفحة إلى متصفح حديث (يدعم SharedArrayBuffer). يرجى تحديث Chrome أو Edge أو Firefox أو Safari إلى أحدث إصدار.
دالة تستدعي نفسها
- التراجع (Recursion) يكون عندما تستدعي الدالة نفسها.
- يجب أن تعمل كل استدعاء على نسخة أصغر من المشكلة.
- عند تطبيقه بشكل صحيح، تتقلص المشكلة حتى تصبح سهلة الحل.
الحالة الأساسية والحالة المتراجعة
- الحالة الأساسية هي أبسط حالة — وهي التي توقف التراجع.
- الحالة المتراجعة تستدعي الدالة مجدداً على إدخال أصغر.
- بدون حالة أساسية لن تتوقف الدالة أبداً (وهذا خطأ).
English
def countdown(n):
if n == 0:
print("Go!")
return
print(n)
countdown(n - 1)
countdown(3)
مثال محلول: المضروب
- المضروب
n!يعنيn × (n-1) × ... × 1. - بالصيغة المتراجعة:
n! = n × (n-1)!، والحالة الأساسية هي0! = 1. - كل استدعاء يضاعف
nمضروباً في مضروب العدد الأقل بمقدار واحد.
English
def factorial(n):
if n == 0:
return 1
return n * factorial(n - 1)
print(factorial(4))
كيف يشغل الكمبيوتر ذلك
- يتم إيقاف كل استدعاء على مكدس الاستدعاءات بينما ينتظر الاستدعاء الداخلي.
- عندما تعيد الحالة الأساسية القيمة، تنتهي الاستدعاءات الموقوفة واحداً تلو الآخر.
- كثرة الاستدعاءات تسبب طفح المكدس — يرفع بايثون
RecursionError.
في الرمز الوهمي لكامبريدج
- الدالة المتراجعة تسمي حالتها الأساسية وحالتها المتراجعة بوضوح.
FUNCTION Factorial(n : INTEGER) RETURNS INTEGER
IF n = 0 THEN
RETURN 1 // base case
ELSE
RETURN n * Factorial(n - 1) // recursive case
ENDIF
ENDFUNCTION
أخطاء شائعة
- كل تراجع يحتاج إلى حالة أساسية، أو سيحدث طفح مكدس الاستدعاءات.
- يجب أن يتحرك كل استدعاء نحو الحالة الأساسية.
الآن جرب بنفسك
- امنح كل دالة حالة أساسية وحالة متراجعة.
- اضغط على تحقق من الإجابة لاختبار الكود الخاص بك.
استكشف
التراجع يرجع من الأوراق
كل استدعاء يتفرع إلى استدعاءات أصغر؛ تُرجع الإجابات صاعدة من الحالات الأساسية.
الصعوبة 4/5 · 280 عملة + مكافأة صغيرة عند الإنجاز الأول اليوم
اكتب دالة تراجعية sum_to(n) ترجع 1 + 2 + ... + n. الحالة الأساسية هي sum_to(0) وهي 0.
اضغط تشغيل لرؤية المخرجات هنا.
الصعوبة 4/5 · 280 عملة + مكافأة صغيرة عند الإنجاز الأول اليوم
اكتب دالة تراجعية power(base, exp) ترجع base مرفوعة للأس exp. الحالة الأساسية هي exp == 0، والتي تعطي 1.
اضغط تشغيل لرؤية المخرجات هنا.
الصعوبة 4/5 · 280 عملة + مكافأة صغيرة عند الإنجاز الأول اليوم
اكتب دالة تراجعية count_up(n) ترجع القائمة [1, 2, ..., n]. الحالة الأساسية هي count_up(0) وهي القائمة الفارغة [].
اضغط تشغيل لرؤية المخرجات هنا.