این آموزش عمیق در مورد Recursion در جاوا توضیح می‌دهد که Recursion چیست با مثال‌ها، انواع و مفاهیم مرتبط. همچنین Recursion vs Iteration را پوشش می‌دهد:
از آموزش‌های قبلی خود در جاوا، ما رویکرد تکراری را دیده‌ایم که در آن یک حلقه را اعلام می‌کنیم و سپس با استفاده از یک عنصر در یک ساختار داده به روشی تکراری عبور می‌کنیم. یک زمان.
ما همچنین جریان شرطی را دیده‌ایم که در آن دوباره یک متغیر حلقه را نگه می‌داریم و یک قطعه کد را تکرار می‌کنیم تا متغیر حلقه با شرط مطابقت کند. وقتی صحبت از فراخوانی تابع می شود، رویکرد تکراری را برای فراخوانی تابع نیز بررسی کردیم> در این آموزش، ما یک رویکرد متفاوت برای برنامه نویسی یعنی رویکرد بازگشتی را مورد بحث قرار خواهیم داد.
بازگشت در جاوا چیست؟
بازگشت فرآیندی است که توسط آن یک تابع یا یک متد بارها و بارها خود را فراخوانی می کند. این تابع که بارها و بارها به طور مستقیم یا غیرمستقیم فراخوانی می شود، "تابع بازگشتی" نامیده می شود.
ما نمونه های مختلفی را برای درک بازگشت مشاهده خواهیم کرد. حال بیایید نحو بازگشت را ببینیم.
Recursion Syntax
هر روشی که Recursion را پیاده سازی می کند دارای دو بخش اساسی است:
- فراخوانی روشی که می‌تواند خود را Recursive بنامد
- پیش‌شرطی که بازگشت را متوقف می‌کند.
توجه داشته باشید که یک پیش‌شرط برای هر روش بازگشتی ضروری است، اگر این کار را نکنیم شکستنبازگشتی پس از آن بی نهایت به کار خود ادامه می دهد و منجر به سرریز پشته می شود.
نحو کلی بازگشت به شرح زیر است:
methodName (T parameters…) { if (precondition == true) //precondition or base condition { return result; } return methodName (T parameters…); //recursive call } توجه داشته باشید که پیش شرط نیز نامیده می شود. وضعیت پایه در بخش بعدی بیشتر در مورد شرط پایه بحث خواهیم کرد.
درک بازگشت در جاوا
در این بخش سعی می کنیم روند بازگشت را درک کنیم و ببینیم که چگونه انجام می شود. ما در مورد شرایط پایه، سرریز پشته یاد خواهیم گرفت و خواهیم دید که چگونه یک مشکل خاص را می توان با بازگشت و جزئیات دیگر حل کرد.
شرایط پایه بازگشتی
در حین نوشتن برنامه بازگشتی، باید ابتدا راه حلی برای کیس پایه ارائه کنید. سپس مسئله بزرگتر را بر حسب مسائل کوچکتر بیان می کنیم.
به عنوان مثال، می توانیم یک مسئله کلاسیک محاسبه فاکتوریل یک عدد را در نظر بگیریم. با توجه به یک عدد n، باید فاکتوریل n را پیدا کنیم که با n مشخص شده است!
حالا اجازه دهید برنامه را برای محاسبه n فاکتوریل (n!) با استفاده از بازگشت پیاده سازی کنیم.
public class Main{ static int fact(int n) { if (n == 1) // base condition return 1; else return n*fact(n-1); } public static void main(String[] args) { int result = fact(10); System.out.println("10! = " + result); } }خروجی
در این برنامه می بینیم که شرط (n=1) شرط پایه است و با رسیدن به این شرط، تابع 1 را برمی گرداند. بخش دیگر تابع فراخوانی بازگشتی است. اما هر بار که روش بازگشتی فراخوانی می شود، n با 1 کاهش می یابد.
بنابراین می توان نتیجه گرفت که در نهایت مقدار n به 1 یا کمتر از 1 تبدیل می شود و در این صورتنقطه، متد مقدار 1 را برمی گرداند. این شرط پایه به دست می آید و تابع متوقف می شود. توجه داشته باشید که مقدار n می تواند هر چیزی باشد تا زمانی که شرط پایه را برآورده کند.
حل مسئله با استفاده از بازگشت
ایده اساسی پشت استفاده از بازگشت این است که مشکل بزرگتر را بر حسب مشکلات کوچکتر همچنین، باید یک یا چند شرط پایه اضافه کنیم تا بتوانیم از حالت بازگشتی خارج شویم.
این قبلاً در مثال فاکتوریل بالا نشان داده شده بود. در این برنامه n فاکتوریل (n!) را بر حسب مقادیر کوچکتر بیان کردیم و شرط پایه (n =1) داشتیم تا وقتی n به 1 رسید، بتوانیم از روش بازگشتی خارج شویم.
خطای سرریز پشته در بازگشت
ما می دانیم که وقتی هر متد یا تابعی فراخوانی می شود، وضعیت تابع در پشته ذخیره می شود و با بازگشت تابع بازیابی می شود. پشته برای روش بازگشتی نیز استفاده می شود.
اما در مورد بازگشت، اگر شرط پایه را تعریف نکنیم یا زمانی که شرط پایه به نحوی به دست نیامده یا اجرا نشود، ممکن است مشکلی رخ دهد. اگر این وضعیت رخ دهد، ممکن است سرریز پشته ایجاد شود.
بیایید مثال زیر از نمادگذاری فاکتوریل را در نظر بگیریم.
در اینجا یک شرط پایه اشتباه داده ایم، n==100.
public class Main { static int fact(int n) { if (n == 100) // base condition resulting in stack overflow return 1; else return n*fact(n-1); } public static void main(String[] args) { int result = fact(10); System.out.println("10! = " + result); } }بنابراین وقتی n > 100 روش 1 را برمی گرداند اما بازگشت متوقف نمی شود. مقدار n به طور نامحدود کاهش می یابدشرط دیگری برای متوقف کردن آن نیست. این کار تا زمانی که پشته سرریز شود ادامه خواهد داشت.
یک مورد دیگر زمانی است که مقدار n 100. در این مورد نیز روش هرگز شرط پایه را اجرا نمی کند و منجر به سرریز پشته می شود.
مثال های بازگشتی در جاوا
در این بخش، مثال های زیر را با استفاده از آن پیاده سازی می کنیم. بازگشتی.
#1) سری فیبوناچی با استفاده از بازگشت
سری فیبوناچی توسط،
1،1،2،3،5،8،13،21، 34,55,…
توالی بالا نشان می دهد که عنصر فعلی حاصل جمع دو عنصر قبلی است. همچنین اولین عنصر در سری فیبوناچی 1 است.
بنابراین به طور کلی اگر n عدد فعلی باشد، با مجموع (n-1) و (n-2) به دست می آید. همانطور که عنصر فعلی بر حسب عناصر قبلی بیان می شود، می توانیم این مشکل را با استفاده از بازگشت بیان کنیم.
برنامه اجرای سری فیبوناچی در زیر آورده شده است:
public class Main { //method to calculate fibonacci series static int fibonacci(int n) { if (n = 1) { return n; } return fibonacci(n-1) + fibonacci(n-2); } public static void main(String[] args) { int number = 10; //print first 10 numbers of fibonacci series System.out.println ("Fibonacci Series: First 10 numbers:"); for (int i = 1; i = number; i++) { System.out.print(fibonacci(i) + " "); } } } خروجی
#2) بررسی کنید که آیا عدد یک پالیندروم است با استفاده از بازگشت
پالیندروم دنباله‌ای است که وقتی ما برابر است آن را از چپ به راست یا راست به چپ بخوانید.
با عدد 121 می بینیم که وقتی آن را از چپ به راست و راست به چپ می خوانیم برابر است. بنابراین عدد 121 یک پالیندروم است.
بیایید یک عدد دیگر، 1242 را در نظر بگیریم. وقتی آن را از چپ به راست می خوانیم، 1242 است و وقتی از راست به چپ خوانده می شود، به عنوان 2421 خوانده می شود. بنابراین این یک پالیندروم نیست.
مابرنامه پالیندروم را با معکوس کردن ارقام اعداد اجرا کنید و عدد داده شده را به صورت بازگشتی با نمایش معکوس آن مقایسه کنید.
برنامه زیر برنامه را برای بررسی پالیندروم اجرا می کند.
import java.io.*; import java.util.*; public class Main { // check if num contains only one digit public static int oneDigit(int num) { if ((num >= 0) && (num 10)) return 1; else return 0; } //palindrome utility function public static int isPalindrome_util (int num, int revNum) throws Exception { // base condition; return if num=0 if (num == 0) { return revNum; } else { //call utility function recursively revNum = isPalindrome_util(num / 10, revNum); } // Check if first digit of num and revNum are equal if (num % 10 == revNum % 10) { // if yes, revNum will move with num return revNum / 10; } else { // exit throw new Exception(); } } //method to check if a given number is palindrome using palindrome utility function public static int isPalindrome(int num) throws Exception { if (num 0) num = (-num); int revNum = (num); return isPalindrome_util(num, revNum); } public static void main(String args[]) { int n = 1242; try { isPalindrome(n); System.out.println("Yes, the given number " + n + " is a palindrome."); } catch (Exception e) { System.out.println("No, the given number " + n + " is not a palindrome."); } n = 1221; try { isPalindrome(n); System.out.println("Yes, the given number " + n + " is a palindrome."); } catch (Exception e) { System.out.println("No, the given number " + n + " is not a palindrome."); } } }خروجی
#3) بازگشت رشته معکوس جاوا
با توجه به رشته "Hello" باید آن را معکوس کنیم تا رشته حاصل "olleH" است.
این با استفاده از بازگشت انجام می شود. با شروع از آخرین کاراکتر در رشته، ما به صورت بازگشتی هر کاراکتر را چاپ می کنیم تا زمانی که همه کاراکترهای رشته تمام شوند.
برنامه زیر از بازگشت برای معکوس کردن یک رشته معین استفاده می کند.
class String_Reverse { //recursive method to reverse a given string void reverseString(String str) { //base condition; return if string is null or with 1 or less character if ((str==null)||(str.length() = 1)) System.out.println(str); else { //recursively print each character in the string from the end System.out.print(str.charAt(str.length()-1)); reverseString(str.substring(0,str.length()-1)); } } } class Main{ public static void main(String[] args) { String inputstr = "SoftwareTestingHelp"; System.out.println("The given string: " + inputstr); String_Reverse obj = new String_Reverse(); System.out.print("The reversed string: "); obj.reverseString(inputstr); } } خروجی
#4) جستجوی باینری بازگشت جاوا
الگوریتم جستجوی دودویی یک الگوریتم معروف برای جستجو است. در این الگوریتم، با توجه به یک آرایه مرتب شده از n عنصر، در این آرایه عنصر کلیدی داده شده را جستجو می کنیم. در ابتدا با یافتن عنصر میانی آرایه، آرایه را به دو نیمه تقسیم می کنیم.
سپس بسته به اینکه کلید میانی باشد، جستجوی خود را در نیمه اول یا دوم آرایه محدود می کنیم. به این ترتیب همین روند تکرار می شود تا زمانی که مکان عناصر کلیدی پیدا شود.
این الگوریتم را با استفاده از بازگشت در اینجا پیاده سازی می کنیم.
import java.util.*; class Binary_Search { // recursive binary search int binarySearch(int numArray[], int left, int right, int key) { if (right >= left) { //calculate mid of the array int mid = left + (right - left) / 2; // if the key is at mid, return mid if (numArray[mid] == key) return mid; // if key key) return binarySearch(numArray, left, mid - 1, key); // Else recursively search in the right subarray return binarySearch(numArray, mid + 1, right, key); } // no elements in the array, return -1 return -1; } } class Main{ public static void main(String args[]) { Binary_Search ob = new Binary_Search(); //declare and print the array int numArray[] = { 4,6,12,16,22}; System.out.println("The given array : " + Arrays.toString(numArray)); int len = numArray.length; //length of the array int key = 16; //key to be searched int result = ob.binarySearch(numArray, 0, len - 1, key); if (result == -1) System.out.println("Element " + key + " not present"); else System.out.println("Element " + key + " found at index " + result); } } خروجی
#5) با استفاده از Recursion، حداقل مقدار را در آرایه پیدا کنید
با استفاده از بازگشت، می‌توانیم حداقل مقدار را در آرایه نیز پیدا کنیم.
0> برنامه جاوا برای یافتن حداقل مقدار در آرایه در زیر آورده شده است.
import java.util.*; class Main { static int getMin(int numArray[], int i, int n) { //return first element if only one element or minimum of the array elements return (n == 1) ? numArray[i] : Math.min(numArray[i], getMin(numArray,i + 1 , n - 1)); } public static void main(String[] args) { int numArray[] = { 7,32,64,2,10,23 }; System.out.println("Given Array : " + Arrays.toString(numArray)); int n = numArray.length; System.out.print("Minimum element of array: " + getMin(numArray, 0, n) + "\n"); } }خروجی
اینها برخی از نمونه های بازگشت جدای از این مثال‌ها، بسیاری از مشکلات دیگر در نرم‌افزار را می‌توان با استفاده از تکنیک‌های بازگشتی پیاده‌سازی کرد.
انواع بازگشت
بر اساس زمانی که تماس برقرار می‌شود، بازگشت به دو نوع است. روش بازگشتی.
آنها عبارتند از:
#1) بازگشت دم
زمانی که فراخوانی روش بازگشتی آخرین عبارت باشد در داخل متد بازگشتی اجرا می شود، به آن "Tail Recursion" می گویند.
در بازگشت دم، دستور فراخوانی بازگشتی معمولاً همراه با عبارت بازگشتی متد اجرا می شود.
نحو کلی برای بازگشت دم در زیر آورده شده است:
methodName ( T parameters…){ { if (base_condition == true) { return result; } return methodName (T parameters …) //tail recursion } #2) بازگشت سر
بازگشت سر هر رویکرد بازگشتی است که یک بازگشت دنباله نیست. بنابراین حتی بازگشت کلی نیز بازگشت به جلو است.
سینتکس بازگشت سر به شرح زیر است:
methodName (T parameters…){ if (some_condition == true) { return methodName (T parameters…); } return result; } بازگشت در مقابل تکرار در جاوا
| Recursion | Iteration |
|---|---|
| Recursion فرآیندی است که در آن یک متد به طور مکرر خود را فراخوانی می کند تا زمانی که یک شرط پایه برآورده شود. | تکرار عبارت است از فرآیندی که توسط آن یک قطعه کد به طور مکرر برای تعداد محدودی بار یا تا زمانی که یک شرط برآورده شود اجرا می شود. |
| آیا برنامه کاربردی برای توابع است. | قابل اجرا است. برای حلقه ها. |
| به خوبی برایاندازه کد کوچکتر. | برای اندازه کد بزرگتر به خوبی کار می کند. |
| از حافظه بیشتری استفاده می کند زیرا هر تماس بازگشتی به پشته فشار داده می شود | حافظه نسبتاً کمتری استفاده می‌شود. |
| اشکال‌زدایی و نگهداری مشکل است | اشکال‌زدایی و نگهداری آسان‌تر |
| در صورت سرریز پشته، در صورت پایه شرط مشخص نشده است یا به دست نیامده است. | ممکن است تا بی نهایت اجرا شود اما در نهایت اجرا با هر گونه خطای حافظه متوقف می شود |
| پیچیدگی زمانی بسیار زیاد است. | پیچیدگی زمانی نسبتاً پایین است. |
سوالات متداول
Q #1) Recursion در جاوا چگونه کار می کند؟
پاسخ: در بازگشت، تابع بازگشتی به طور مکرر خود را فراخوانی می کند تا زمانی که یک شرط پایه برآورده شود. حافظه تابع فراخوانی شده به پشته در بالای حافظه برای تابع فراخوانی فشار داده می شود. برای هر فراخوانی تابع، یک کپی جداگانه از متغیرهای محلی ساخته می شود.
Q #2) چرا از Recursion استفاده می شود؟
پاسخ: بازگشت برای حل مسائلی استفاده می شود که می توان آنها را به مسائل کوچکتر تقسیم کرد و کل مسئله را می توان در قالب یک مسئله کوچکتر بیان کرد. پیچیده با استفاده از رویکرد تکراری حل می شود. علاوه بر مشکلاتی که پیچیدگی زمانی برای آنها مهم نیست، از بازگشت استفاده کنید.
Q #3) مزایایبازگشت؟
پاسخ:
مزایای Recursion عبارتند از:
- Recursion تماس اضافی را کاهش می دهد از تابع.
- بازگشت به ما اجازه می‌دهد در مقایسه با رویکرد تکراری، مسائل را به راحتی حل کنیم.
Q #4) کدام یک بهتر است - بازگشت یا تکرار؟
پاسخ: Recursion تماس‌های مکرر را تا رسیدن به عملکرد پایه برقرار می‌کند. بنابراین یک حافظه سربار وجود دارد، زیرا یک حافظه برای هر فراخوانی تابع به پشته فشار داده می شود.
از سوی دیگر، تکرار سربار حافظه زیادی ندارد. اجرای بازگشتی کندتر از رویکرد تکراری است. بازگشت اندازه کد را کاهش می دهد در حالی که رویکرد تکراری کد را بزرگ می کند.
Q #5) مزایای بازگشت نسبت به تکرار چیست؟
پاسخ:
- بازگشت کد را واضح تر و کوتاه تر می کند.
- بازگشت بهتر از رویکرد تکراری برای مشکلاتی مانند برج هانوی، درخت است. پیمایش ها و غیره.
- از آنجایی که هر فراخوانی تابع دارای حافظه است که به پشته فشار داده می شود، Recursion از حافظه بیشتری استفاده می کند.
- عملکرد بازگشتی کندتر از رویکرد تکراری است.
نتیجه
بازگشت یک مفهوم بسیار مهم در نرم افزار صرف نظر از زبان برنامه نویسی است. Recursion بیشتر در حل مشکلات ساختار داده مانند برج های هانوی، پیمایش درختان، لیست های پیوندی و غیره استفاده می شود.بازگشت کد را ساده تر و واضح تر می کند.
ما در این آموزش همه چیز را در مورد Recursion بررسی کرده ایم. ما همچنین نمونه های برنامه نویسی متعددی را برای درک بهتر مفهوم پیاده سازی کرده ایم.