این چالش با نوشتن توابع بازگشتی و پوشش الگوریتم اقلیدسی برای یافتن بزرگ‌ترین مقسوم‌علیه مشترک (GCD) دو عدد سر و کار دارد. الگوریتم اقلیدسی اولین بار توسط ریاضیدان یونانی اقلیدس توصیف شده است.

الگوریتم

برای ساده‌تر کردن توضیحات، عدد اول را “a”، عدد دوم را “b”، و باقی‌مانده را “r” می‌نامیم. مراحل الگوریتم به صورت زیر است:

1. مطمئن شوید که “a” >= “b”. اگر “a” < “b”، جای آن‌ها را عوض کنید.
2. باقی‌مانده را پیدا کنید. “a” را بر “b” تقسیم کنید و مقدار باقی‌مانده را به “r” اختصاص دهید.
3. آیا مقدار “r” صفر است؟ اگر بله، تابع را متوقف کرده و مقدار “b” (عدد دوم) را بازگردانید.
4. مقدار “a” را برابر با “b” و مقدار “b” را برابر با “r” قرار دهید و الگوریتم را دوباره از ابتدا شروع کنید.

دستورالعمل‌ها

یک تابع بازگشتی بنویسید که با استفاده از الگوریتم اقلیدسی، بزرگ‌ترین مقسوم‌علیه مشترک (GCD) بین دو عدد مثبت را بازگرداند.

Euclidean(8, 6) ➞ 2

Euclidean(25, 5) ➞ 5

Euclidean(49, 14) ➞ 7

نکات

1. برای پیدا کردن باقی‌مانده دو عدد از عملگر % (modulus) استفاده کنید.
2. هر دو عدد مثبت خواهند بود و هیچ‌کدام مقدار صفر ندارند.
3. بسیاری از چالش‌های این مجموعه می‌توانند به صورت غیر بازگشتی و بدون پیاده‌سازی الگوریتم‌های توضیح داده شده حل شوند. اما توصیه می‌کنم که این چالش‌ها را همان‌طور که توضیح داده شده است، حل کنید. درک نکردن مفاهیم آموزش داده شده می‌تواند مانعی برای چالش‌های بعدی باشد و به ارتقای مهارت‌های شما به‌عنوان برنامه‌نویس کمک نخواهد کرد.