بازگشت 遞迴 – انجمن DEV

در مرحله بعد، اگر می خواهید به آرامی اصول مربوط به CS خود را جبران کنید و بیشتر در معرض دانش فنی گسترده قرار بگیرید، بیایید با بازگشت شروع کنیم!

🐳 انواع بازگشت

اگر در یک تابع یک توصیف خود فراخوانی وجود داشته باشد، آن را بازگشتی می‌توان تقریباً به سه دسته تقسیم کرد:

• بازگشت مستقیم
• بازگشت غیر مستقیم
• بازگشت دم

در اینجا چند مثال ساده برای نشان دادن این سه بازگشت آورده شده است.

🦀 بازگشت مستقیم

بازگشت مستقیم باید به راحتی قابل درک باشد. اگر تابعی خود را درون یک تابع فراخوانی کند، بازگشت مستقیم نامیده می شود. می توانید به کد psuedo زیر مراجعه کنید:

void directRecursionFunction()
{
  // some code...

  directRecursionFunction();

  // some code...
}

🦀 بازگشت غیر مستقیم

بازگشت غیر مستقیم به این معنی است که چندین ماژول با یکدیگر تماس می گیرند تا یک چرخه فراخوانی تشکیل دهند. به عنوان مثال: فرض کنید در حال حاضر سه تابع وجود دارد:module A،module B،module C، این سه تابع یکدیگر را فراخوانی می کنند که مانند شکل زیر بازگشت غیر مستقیم را تشکیل می دهند:

مانند وضعیت فوق که توابع یکدیگر را صدا می کنند و به شدت به یکدیگر وابسته هستند (کوپلینگ بالا)، سعی کنید آن را در توسعه واقعی ننویسید، بسیار ترسناک خواهد بود.

🦀 بازگشت دم

Tail Recursion در واقع نوعی بازگشت مستقیم است، اما پس از بازگشت، دستور اجرایی بعدی عبارت END است. این دسته به طور خاص جدا شده است زیرا این نوع بازگشت را می توان در کامپایلر بهینه کرد. (معنای بهینه سازی را می توان تا حدی به صورت «تغییر بازگشت به غیر بازگشتی» فهمید)

🐳 بازگشت در مقابل تکرار (غیر بازگشتی)

• راه حل هر مسئله ای باید با دو الگوریتم حل شود: بازگشتی و غیر بازگشتی.
• الگوریتم های بازگشتی و غیر بازگشتی را می توان به یکدیگر تبدیل کرد
  • بازگشتی به غیر بازگشتی تغییر می کند و یک SOP استاندارد وجود دارد
  • تغییر از غیر بازگشتی به بازگشتی، هیچ SOP استانداردی وجود ندارد (نیاز به الهام گرفتن)

نمودار شماتیک

چارت مقایسه

🐳 تمرین سوال

🦀 فاکتوریل N!

سوال 1: یک تابع تعاملی Fac(N) یا شبه کد برای N بنویسید!

function fac(n) {
  let result = 1;
  for (let i = 1; i <= n; i++>) {
    result = result * i;
  }
  return result;
}

سوال 2: یک تابع بازگشتی Fac(N) یا شبه کد برای N بنویسید!

ابتدا تعریف ریاضی بازگشتی فاکتوریل را بنویسید:

سپس کد بازگشتی را بنویسید:

function fac(n) {
  if (n === 0) {
    return 1;
  } else {
    return fac(n-1) * n;
  }
}

ترفند حل مسائل مربوط به بازگشت: ابتدا تعریف ریاضی بازگشت را ارائه دهید و سپس تعریف ریاضی را به کد برنامه تبدیل کنید!

🦀 عدد فیبوناچی

تعریف

سوال 1: یک تابع بازگشتی برای Fib(N) بنویسید

function fib(n) {
  if (n === 0) {
    return 0;
  }
  if (n === 1) {
    return 1;
  }
  return fib(n-1) + fib(n-2);
}

سوال 2: یک تابع تعاملی برای Fib(N) بنویسید

function fib(n) {
  if (n === 0) {
    return 0;
  } else if (n === 1) {
    return 1;
  } else {
    let a = 0;
    let b = 1;
    let c;
    for (let i = 2; i <= n; i++) {
      c = a + b;
      a = b;
      b = c;
    }
    return c;
  }
}

🦀 Greatest Common Divisor (GCD) Greatest Common Divisor

تعریف

از تقسیم اقلیدسی برای محاسبه بزرگترین عامل مشترک دو عدد (A, B) استفاده کنید که به صورت زیر تعریف می شود:

کد بازگشتی را برای GCD (A, B) بنویسید

function gcd(a, b) {
  if (a % b === 0) return b;
  return gcd(b, a % b);
}

🦀 برج هانوی برج هانوی

توضیحات عنوان

سه ستون وجود دارد، با فرض اینکه آنها A، B و C نامیده می شوند. n صفحه با اندازه های مختلف روی ستون A وجود دارد. صفحات بر اساس اندازه از بالا به پایین مرتب شده اند بزرگترین اکنون باید صفحات را از ستون A به ستون C منتقل کنیم، اما قوانین زیر باید رعایت شود:

1. فقط یک صفحه را می توان در یک زمان جابجا کرد
2. بشقاب های بزرگ را روی بشقاب های کوچک قرار ندهید

لطفاً تمام مراحل حرکت را چاپ کنید.

ایده های حل مسئله

       A            B           C

       │            │           │
       │            │           │
       │            │           │
1    ┌─┼─┐          │           │
2   ┌┼┼┼┼┼┐         │           │
3  ┌┼┼┼┼┼┼┼┐        │           │
  ─┴───────┴─   ────┴────   ────┴────

بیایید با یک مثال شروع کنیم: فرض کنید در حال حاضر سه ستون A، B و C وجود دارد و سه صفحه روی ستون A وجود دارد. مراحل به شرح زیر است:

1. دیسک 1 را از A به C منتقل کنید
2. دیسک 2 را از A به B منتقل کنید
3. دیسک 1 را از C به B منتقل کنید
4. دیسک 3 را از A به C منتقل کنید
5. دیسک 1 را از B به A منتقل کنید
6. دیسک 2 را از B به C منتقل کنید
7. دیسک 1 را از A به C منتقل کنید

بیایید مراحل را به سه بلوک تقسیم کنیم:

1. مراحل 1. ~ 3. مراحل حرکت صفحات شماره 1 ~ 2 از ستون A به ستون B است.
2. مرحله 4. آخرین مرحله این است که آخرین صفحه شماره 3 را مستقیماً از ستون A به ستون C منتقل کنید.
3. مرحله بعدی این است که تمام صفحات روی ستون B را به ستون C منتقل کنید.

استثنا: اگر فقط یک صفحه وجود دارد، فقط آن را مستقیماً از ستون A به ستون C منتقل کنید.

function hanoi(n, from, to, via) {
  if (n === 1) {
    console.log(`move disk 1 from ${from} to ${to}`);
  } else {
    hanoi(n - 1, from, via, to); // 先把 n - 1 個盤子都移到中間的柱子
    console.log(`move disk ${n} from ${from} to ${to}`); // 把最下面的盤子移到目標柱子
    hanoi(n - 1, via, to, from); // 再把剩下的 n - 1 個盤子移到目標柱子
  }
}

تعریف بازگشتی برج هانوی

مراحل ذکر شده در بالا را با استفاده از فرمول های ریاضی بیان کنید،

$T(n)$

حرکت را نشان می دهد

$n$

تعداد اجراهای مورد نیاز برنامه برای هر صفحه، در صورت حل شدن

$T(n)$

این بدان معنی است که پیچیدگی زمانی این تابع حل شده است:

باز کردن

$T(n)$

، از روش جایگزینی گسترش استفاده کنید: