🔹 تعریف

• Recursion یعنی یک تابع خودش را فراخوانی می‌کند.

• کاربرد: حل مسائل تکراری یا تقسیم‌شونده مثل فاکتوریل، فیبوناچی و جستجو در درخت‌ها.

🔹 ساختار کلی

return_type function_name(parameters) {
    if (base_condition) {
        return base_value;  // شرط پایان بازگشت
    }
    else {
        // فراخوانی تابع با ورودی کوچک‌تر
        return function_name(smaller_input);
    }
}

Base Case: شرط پایان بازگشت، ضروری است تا از بی‌نهایت شدن تابع جلوگیری شود.

1️⃣ مثال: فاکتوریل عدد

#include <iostream>
using namespace std;

int factorial(int n) {
    if(n == 0) return 1;   // Base Case
    return n * factorial(n-1); // Recursive Call
}

int main() {
    int num = 5;
    cout << "Factorial of " << num << " is " << factorial(num) << endl; // 120
}

2️⃣ مثال: دنباله فیبوناچی

#include <iostream>
using namespace std;

int fibonacci(int n) {
    if(n == 0) return 0;
    if(n == 1) return 1;
    return fibonacci(n-1) + fibonacci(n-2);
}

int main() {
    int n = 7;
    cout << "Fibonacci of " << n << " is " << fibonacci(n) << endl; // 13
}

3️⃣ مثال: چاپ آرایه به صورت بازگشتی

#include <iostream>
using namespace std;

void printArray(int arr[], int size) {
    if(size == 0) return;          // Base Case
    printArray(arr, size-1);       // Recursive Call
    cout << arr[size-1] << " ";    // چاپ بعد از بازگشت
}

int main() {
    int arr[] = {1, 2, 3, 4, 5};
    int size = sizeof(arr)/sizeof(arr[0]);
    printArray(arr, size);         // خروجی: 1 2 3 4 5
}

🔹 نکات مهم

1. Base Case الزامی است تا از Stack Overflow جلوگیری شود.

2. بازگشت تابع به صورت LIFO (Last In First Out) انجام می‌شود.

3. Recursion برای مسائل تکراری و تقسیم‌شونده بسیار مناسب است.

4. برای آرایه‌ها، لیست‌ها و درخت‌ها استفاده زیادی دارد.

5. Recursion ممکن است مصرف حافظه بیشتری نسبت به حلقه‌ها داشته باشد، مخصوصاً برای n بزرگ.