بازگشتی (Recursion)

آشنایی با توابع بازگشتی در C++ و نحوه استفاده از آن‌ها

بازگشتی (Recursion)

بازگشتی زمانی رخ می‌دهد که یک تابع خودش را فراخوانی کند. این تکنیک برای حل مسائلی که می‌توانند به زیرمسائل کوچکتر تقسیم شوند، مفید است.

ساختار تابع بازگشتی

returnType recursiveFunction(parameters) {
    // حالت پایه (Base Case)
    if (baseCondition) {
        return baseValue;
    }
    
    // حالت بازگشتی (Recursive Case)
    return recursiveFunction(modifiedParameters);
}

مثال 1: فاکتوریل

int factorial(int n) {
    // حالت پایه
    if (n <= 1) {
        return 1;
    }
    
    // حالت بازگشتی
    return n * factorial(n - 1);
}

int main() {
    cout << "5! = " << factorial(5);  // 120
    return 0;
}

مثال 2: فیبوناچی

int fibonacci(int n) {
    // حالت پایه
    if (n <= 1) {
        return n;
    }
    
    // حالت بازگشتی
    return fibonacci(n - 1) + fibonacci(n - 2);
}

int main() {
    for (int i = 0; i < 10; i++) {
        cout << fibonacci(i) << " ";
    }
    // خروجی: 0 1 1 2 3 5 8 13 21 34
    return 0;
}

مثال 3: توان

double power(double base, int exponent) {
    // حالت پایه
    if (exponent == 0) {
        return 1;
    }
    
    // حالت بازگشتی
    return base * power(base, exponent - 1);
}

int main() {
    cout << "2^5 = " << power(2, 5);  // 32
    return 0;
}

مثال 4: معکوس رشته

#include <string>
using namespace std;

string reverseString(string str) {
    // حالت پایه
    if (str.length() <= 1) {
        return str;
    }
    
    // حالت بازگشتی
    return reverseString(str.substr(1)) + str[0];
}

int main() {
    cout << reverseString("Hello");  // olleH
    return 0;
}

مثال 5: جستجوی دودویی

int binarySearch(int arr[], int left, int right, int target) {
    // حالت پایه: عنصر پیدا نشد
    if (left > right) {
        return -1;
    }
    
    int mid = left + (right - left) / 2;
    
    // عنصر پیدا شد
    if (arr[mid] == target) {
        return mid;
    }
    
    // جستجو در نیمه چپ
    if (arr[mid] > target) {
        return binarySearch(arr, left, mid - 1, target);
    }
    
    // جستجو در نیمه راست
    return binarySearch(arr, mid + 1, right, target);
}

مزایای بازگشتی

معایب بازگشتی

بهترین شیوه‌ها

نکات مهم

این مبحث بخشی از دوره آموزش کامل C++ است.

ابزارهای مرتبط