جایگزین تابع بازگشتی

[lmaghsoodi]

با سلام خدمت دوستان گرامی
من می خواهم بدانم آیا می توان برای توابع بازگشتی جایگزینی قرار داد که performance با لای رود به عنوان مثال
f(n) =f(n-2) + (fn-1) به جای آن بایستی چه کاری اجام دهیم؟

[Raminab]

سلام

خب به نظر من کاملا بستگی به مساله ی شما داره , برای این مثال که زدید حل به روش بازگشتی گزینه ی خوبی نیست دلیلشم اینکه محاسبات خیلی زیادی به صورت تکراری انجام میشه مثلا برای فیب 20 لازمه فیب 19 و 18 رو بدست بیارید بعد برای فیب 19 لازمه فیب 18 و 17 رو بدست بیارید و برای فیب 18 لازمه فیب 17 و 16 و همینجور نگاه کنید میبینید چقد محاسبات تکراری زیاده 136458
برای این مساله اگر از اول با قانون اینکه 2 جمله اول فیبوناچی 1 (در بعضی کتاب ها گفته شده 0 و 1 ) هستند و از شروع از جملات اول جملات بعدی رو بدست بیارین خیلی بهتره (sequentioal). کد هم توی نت زیاده. تازه ی فرمول هم بود که جمله n دنباله رو بدست میاورد الان یادم نیست :لبخند:
ولی درکل نمیشه گفت هر بازگشتی رو میشه با هزینه کمتری نوشت

[ahmad.mo74]

سلام

شما اول باید با روش (dp (Dynamic Programming (https://en.wikipedia.org/wiki/Dynamic_programming) آشنا بشید.
مهم ترین چیزی که روش dp میگه اینه که هیچ زیر مسئله رو بیش از یکبار نباید حل نکنید.
همونطور که آقای Raminab با شکل هم نشون دادن، چندین زیر مسئله رو داریم چندین بار حل میکنیم.

برای حل این موضوع معمولا از تکنیک هایی مثل (Memoization (top-down و (Tabulation (bottom-up استفاده میشه.

اول Memoization رو توضیح میدم که آسون تره.
توی این روش خیلی ساده مثل قبل کارمون رو انجام میدیم ولی با این تفاوت که هربار جواب هامونو یه جایی نگه میداریم (cache) و برای دفعات بعدی چک میکنیم که اگر داشتیمش از همون استفاده میکنیم و دوباره (زیر) مسئله رو حل نمیکنیم.
مثلا برای همین فیبوناچی :


static final Map<Integer, Integer> FIB_CACHE = new HashMap<>();


static {
FIB_CACHE.put(1, 1);
FIB_CACHE.put(2, 1);
}


static int fib(int fibIndex) {
if (fibIndex < 1) {
throw new IllegalArgumentException("fibIndex starts at 1");
}
Integer v = FIB_CACHE.get(fibIndex);
if (v != null) {
return v;
}
v = fib(fibIndex - 1) + fib(fibIndex - 2);
FIB_CACHE.put(fibIndex, v);
return v;
}


اما روش bottom-up یه خورده پیچیده تره.
تو این این روش ما اول زیر مسئله های کوچیکتر رو حل میکنیم تا بتونیم جواب مسئله های بزرگتر رو راحت تر به دست بیاریم تا برسیم به جواب نهایی.
مثلا برای به دست آوردن (fib(10 اول میایم (fib(1 و (fib(2 و ... حساب میکنیم تا برسیم به (fib(10.
تو این روش هم نوع دیگه ای از caching رو داریم استفاده میکنیم و انگار داریم یه جدول رو از پایین به بالا پر میکنیم و برای پر کردن خونه های بالاتر جدول از خونه های پایینی کمک میگیرم.
اما همیشه انقد آسون نیست و یه وقتایی فهمیدن اینکه زیر مسئله هارو چطوری باید حل کنیم سخت میشه.

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


static int fib(int fibIndex) {
if (fibIndex < 1) {
throw new IllegalArgumentException("fibIndex starts at 1");
}
int[] table = new int[fibIndex + 1];
table[0] = 0;
table[1] = 1;
for (int i = 2; i <= fibIndex; i++) {
table[i] = table[i - 1] + table[i - 2];
}
return table[fibIndex];
}


یا :


static int fib(int fibIndex) {
if (fibIndex < 1) {
throw new IllegalArgumentException("fibIndex starts at 1");
}
int prev = 1, current = 1, temp;
for (int i = 2; i < fibIndex; i++) {
temp = prev;
prev = current;
current = temp + prev;
}
return current;
}


public static void main(String[] args) {
for (int i = 1; i <= 10; i++) {
System.out.printf("fib(%d) = %d%n", i, fib(i));
}
}