بازگشت (Recursion)

بازگشت چیست؟

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

دو بخش ضروری

1. شرط پایه (Base Case): توقف بازگشت — بدون آن، StackOverflow!
2. گام بازگشتی: فراخوانی با ورودی کوچکتر

فاکتوریل

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

factorial(5)
← 5 × factorial(4)
← 5 × 4 × factorial(3)
← 5 × 4 × 3 × factorial(2)
← 5 × 4 × 3 × 2 × factorial(1)
← 5 × 4 × 3 × 2 × 1 = 120

فیبوناچی

static int fib(int n) {
    if (n <= 1) {
        return n;
    }
    return fib(n - 1) + fib(n - 2);
}

fib(10)   ← 55

جمع آرایه به‌صورت بازگشتی

static int sum(int[] arr, int n) {
    if (n == 0) {
        return 0;
    }
    return arr[n - 1] + sum(arr, n - 1);
}

توان به‌صورت بازگشتی

static int power(int base, int exp) {
    if (exp == 0) {
        return 1;
    }
    return base * power(base, exp - 1);
}

power(2, 8)   ← 256

بازگشت در مقابل حلقه