Recursion · العودية
This page needs a recent browser (with SharedArrayBuffer support). Please update Chrome, Edge, Firefox or Safari to the latest version. · تحتاج هذه الصفحة إلى متصفح حديث (يدعم SharedArrayBuffer). يرجى تحديث Chrome أو Edge أو Firefox أو Safari إلى أحدث إصدار.
English
A function that calls itself
- Recursion is when a function calls itself.
- Each call should work on a smaller version of the problem.
- Done right, the problem shrinks until it is trivial to solve.
العربية
دالة تستدعي نفسها
- التراجع (Recursion) يكون عندما تستدعي الدالة نفسها.
- يجب أن تعمل كل استدعاء على نسخة أصغر من المشكلة.
- عند تطبيقه بشكل صحيح، تتقلص المشكلة حتى تصبح سهلة الحل.
English
Base case and recursive case
- The base case is the simplest case — it stops the recursion.
- The recursive case calls the function again on a smaller input.
- Without a base case the function never stops (an error).
العربية
الحالة الأساسية والحالة المتراجعة
- الحالة الأساسية هي أبسط حالة — وهي التي توقف التراجع.
- الحالة المتراجعة تستدعي الدالة مجدداً على إدخال أصغر.
- بدون حالة أساسية لن تتوقف الدالة أبداً (وهذا خطأ).
def countdown(n):
if n == 0:
print("Go!")
return
print(n)
countdown(n - 1)
countdown(3)
English
A worked example: factorial
- The factorial
n!meansn × (n-1) × ... × 1. - In recursive form:
n! = n × (n-1)!, and the base case is0! = 1. - Each call multiplies
nby the factorial of one less.
العربية
مثال محلول: المضروب
- المضروب
n!يعنيn × (n-1) × ... × 1. - بالصيغة المتراجعة:
n! = n × (n-1)!، والحالة الأساسية هي0! = 1. - كل استدعاء يضاعف
nمضروباً في مضروب العدد الأقل بمقدار واحد.
def factorial(n):
if n == 0:
return 1
return n * factorial(n - 1)
print(factorial(4))
English
How the computer runs it
- Each call is paused on a call stack while it waits for the inner call.
- When the base case returns, the paused calls finish one by one.
- Too many calls overflow the stack — Python raises a
RecursionError.
العربية
كيف يشغل الكمبيوتر ذلك
- يتم إيقاف كل استدعاء على مكدس الاستدعاءات بينما ينتظر الاستدعاء الداخلي.
- عندما تعيد الحالة الأساسية القيمة، تنتهي الاستدعاءات الموقوفة واحداً تلو الآخر.
- كثرة الاستدعاءات تسبب طفح المكدس — يرفع بايثون
RecursionError.
English
In Cambridge pseudocode
- A recursive function names its base case and recursive case clearly.
العربية
في الرمز الوهمي لكامبريدج
- الدالة المتراجعة تسمي حالتها الأساسية وحالتها المتراجعة بوضوح.
FUNCTION Factorial(n : INTEGER) RETURNS INTEGER
IF n = 0 THEN
RETURN 1 // base case
ELSE
RETURN n * Factorial(n - 1) // recursive case
ENDIF
ENDFUNCTION
English
Common mistakes
- Every recursion needs a base case, or it overflows the call stack.
- Each call must move closer to the base case.
العربية
أخطاء شائعة
- كل تراجع يحتاج إلى حالة أساسية، أو سيحدث طفح مكدس الاستدعاءات.
- يجب أن يتحرك كل استدعاء نحو الحالة الأساسية.
English
Now you try
- Give each function a base case and a recursive case.
- Press Check answer to test your code.
العربية
الآن جرب بنفسك
- امنح كل دالة حالة أساسية وحالة متراجعة.
- اضغط على تحقق من الإجابة لاختبار الكود الخاص بك.
Explore · استكشف
Recursion returns from the leaves · التراجع يرجع من الأوراق
Each call splits into smaller calls; answers return up from the base cases. · كل استدعاء يتفرع إلى استدعاءات أصغر؛ تُرجع الإجابات صاعدة من الحالات الأساسية.
Write a recursive sum_to(n) that returns 1 + 2 + ... + n. The base case is sum_to(0) which is 0. · اكتب دالة تراجعية sum_to(n) ترجع 1 + 2 + ... + n. الحالة الأساسية هي sum_to(0) وهي 0.
Click Run to see the output here. · اضغط تشغيل لرؤية المخرجات هنا.
Write a recursive power(base, exp) that returns base raised to exp. The base case is exp == 0, which gives 1. · اكتب دالة تراجعية power(base, exp) ترجع base مرفوعة للأس exp. الحالة الأساسية هي exp == 0، والتي تعطي 1.
Click Run to see the output here. · اضغط تشغيل لرؤية المخرجات هنا.
Write a recursive count_up(n) that returns the list [1, 2, ..., n]. The base case is count_up(0) which is the empty list []. · اكتب دالة تراجعية count_up(n) ترجع القائمة [1, 2, ..., n]. الحالة الأساسية هي count_up(0) وهي القائمة الفارغة [].
Click Run to see the output here. · اضغط تشغيل لرؤية المخرجات هنا.