Recursion | التكرار الذاتي

إيه هو الـ Recursion؟

🔄 الفكرة الأساسية

📖 تشبيه المرايا

تخيل إنك واقف بين مرايتين متقابلتين... هتشوف انعكاس جوه انعكاس جوه انعكاس... لانهاية!

الـ Recursion نفس الفكرة: Function بتنادي نفسها، بس لازم يكون فيه نقطة توقف!

⚙️ العناصر الأساسية

🛑

Base Case (حالة التوقف)

الشرط اللي يخلي الـ function توقف عن نداء نفسها

⚠️ من غيرها = Stack Overflow!

🔄

Recursive Case

الـ function بتنادي نفسها بـ input أصغر

لازم نقرب من الـ Base Case!

📚 الـ Call Stack

كل مرة الـ function بتنادي نفسها، الكمبيوتر بيحفظ الحالة الحالية في Call Stack (زي كومة أطباق).

• كل نداء جديد → طبق جديد فوق الكومة
• لما الـ function ترجع → نشيل الطبق من فوق
• لو الكومة تكبر أوي → Stack Overflow! 💥

Example 1: Factorial

مثال: حساب المضروب (Factorial)

📐 إيه هو الـ Factorial؟

n! = ضرب كل الأرقام من 1 لـ n

5! = 5 × 4 × 3 × 2 × 1 = 120

3! = 3 × 2 × 1 = 6

1! = 1

0! = 1 (بالتعريف)

🔄 الـ Recursive Definition

Base Case: 0! = 1

Recursive: n! = n × (n-1)!

5! = 5 × 4!
4! = 4 × 3!
... وهكذا لحد ما نوصل لـ 0!

Try It: Factorial

Call Stack will appear here

factorial.js

function factorial(n) {
  // Base Case: stop here!
  if (n === 0) {
    return 1;
  }
  
  // Recursive Case: n! = n × (n-1)!
  return n * factorial(n - 1);
}

شرح الكود 📖

سطر 3-4: الـ Base Case - لو n = 0، ارجع 1 واوقف!

سطر 8: الـ Recursive Case - اضرب n في factorial(n-1)

⏱️ التعقيد: O(n) time, O(n) space (call stack)

Example 2: Fibonacci

مثال: متتالية فيبوناتشي

🌿 إيه هي متتالية Fibonacci؟

كل رقم = مجموع الرقمين اللي قبله

0, 1, 1, 2, 3, 5, 8, 13, 21, 34...

Base Cases:

fib(0) = 0

fib(1) = 1

Recursive:

fib(n) = fib(n-1) + fib(n-2)

⚠️ تحذير!

الـ naive recursive Fibonacci بطيء جداً: O(2ⁿ)!
لأن بيحسب نفس القيم كتير.

Try It: Fibonacci

Recursion tree will appear here

fibonacci.js

// ⚠️ Naive approach - O(2ⁿ)
function fib(n) {
  if (n <= 1) return n;
  return fib(n - 1) + fib(n - 2);
}

// ✅ Better: Memoization - O(n)
function fibMemo(n, memo = {}) {
  if (n <= 1) return n;
  if (memo[n]) return memo[n];
  memo[n] = fibMemo(n-1, memo) + fibMemo(n-2, memo);
  return memo[n];
}

شرح الكود 📖

Naive (بطيء): بيحسب fib(3) مثلاً مرات كتير!

Memoization (سريع): بنحفظ النتايج اللي حسبناها في object

💡 Memoization: تقنية لتخزين نتايج الحسابات المتكررة

Example 3: Simple Countdown

مثال بسيط: العد التنازلي

function countdown(n) {
  // Base Case
  if (n <= 0) {
    console.log("Blastoff! 🚀");
    return;
  }
  
  // Recursive Case
  console.log(n);
  countdown(n - 1);
}

countdown(5);
// Output: 5, 4, 3, 2, 1, Blastoff! 🚀

Try It: Countdown

Countdown will appear here

Recursion vs Iteration

المقارنة	Recursion	Iteration (Loop)
الكود	أنظف وأقصر عادة	أطول أحياناً
الذاكرة	O(n) - Call Stack	O(1) - أقل
الأداء	Overhead من النداءات	أسرع عادة
أفضل لـ	Trees, Graphs, Divide & Conquer	Simple loops, Fixed iterations