Recursion In Java - مثالن سان سبق

جاوا ۾ Recursion ڇا آهي؟
جاوا ۾ ريٽرن بمقابله تکرار
- اڪثر پڇيا ويندڙ سوال
نتيجو

جاوا ۾ Recursion تي هي گہرائي وارو سبق وضاحت ڪري ٿو ته Recursion ڇا آهي مثالن، قسمن ۽ لاڳاپيل تصورن سان. اهو پڻ احاطه ڪري ٿو Recursion Vs Iteration:

جاوا ۾ اسان جي اڳوڻين سبقن مان، اسان ڏٺا اڪراتي اپروچ جنهن ۾ اسان هڪ لوپ جو اعلان ڪريون ٿا ۽ پوءِ ڊيٽا جي ڍانچي ذريعي ٻيهر ورجائي طريقي سان هڪ عنصر کڻي a time.

اسان Conditional flow پڻ ڏٺو آهي جتي ٻيهر اسان هڪ لوپ ويريبل رکون ٿا ۽ ڪوڊ جي هڪ ٽڪري کي ورجائيندا آهيون جيستائين لوپ ويريبل شرط پوري نه ڪري. جڏهن اها فنڪشن ڪالز جي ڳالهه اچي ٿي، اسان فنڪشن ڪالن لاءِ پڻ اڀرندڙ طريقي جي ڳولا ڪئي آهي> هن سبق ۾، اسان پروگرامنگ جي هڪ مختلف طريقي تي بحث ڪنداسين يعني Recursive اپروچ.

جاوا ۾ Recursion ڇا آهي؟

Recursion ھڪڙو عمل آھي جنھن ذريعي ڪو فنڪشن يا طريقو پاڻ کي بار بار سڏيندو آھي. هي فنڪشن جنهن کي بار بار سڏيو وڃي ٿو سڌو يا اڻ سڌي طرح ”ريڪرسيو فنڪشن“ سڏجي ٿو.

ريڪرشن کي سمجهڻ لاءِ اسان مختلف مثالون ڏسنداسين. ھاڻي اچو ته recursion جي نحو کي ڏسو.

Recursion Syntax

ڪوبه طريقو جيڪو Recursion کي لاڳو ڪري ٿو ان جا ٻه بنيادي حصا آھن:

ريڪرشن جو عام نحو هن ريت آهي:

methodName (T parameters…) { if (precondition == true) //precondition or base condition { return result; } return methodName (T parameters…); //recursive call }

ياد رهي ته اڳڪٿي به سڏجي ٿي. بنيادي حالت. اسان ايندڙ سيڪشن ۾ بنيادي حالت بابت وڌيڪ بحث ڪنداسين.

جاوا ۾ ريٽرننگ کي سمجھڻ

هن سيڪشن ۾، اسين ٻيهر ڪرنسي جي عمل کي سمجهڻ جي ڪوشش ڪنداسين ۽ ڏسو ته اهو ڪيئن ٿئي ٿو. اسان بنيادي حالت، اسٽيڪ اوور فلو جي باري ۾ سکنداسين، ۽ ڏسنداسين ته ڪيئن هڪ خاص مسئلو ٻيهر ڪرنسي ۽ ٻين اهڙن تفصيلن سان حل ڪري سگهجي ٿو.

ريٽرن بيس حالت

ريڪرسيو پروگرام لکڻ دوران، اسان کي گهرجي. پهرين بنيادي ڪيس لاء حل مهيا ڪريو. پوءِ اسان وڏي مسئلي کي ننڍڙن مسئلن جي صورت ۾ ظاهر ڪريون ٿا.

هڪ مثال طور، اسان هڪ عدد جي فيڪٽري کي ڳڻڻ جو هڪ کلاسک مسئلو وٺي سگهون ٿا. هڪ عدد n ڏنو ويو، اسان کي 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 جو قدر ڪجھ به ٿي سگھي ٿو جيستائين اھو بنيادي حالت کي پورو ڪري.

Recursion استعمال ڪندي مسئلو حل ڪرڻ

Recursion استعمال ڪرڻ جي پويان بنيادي خيال آھي وڏي مسئلي کي بيان ڪرڻ ننڍا مسئلا. انهي سان گڏ، اسان کي هڪ يا وڌيڪ بنيادي حالتون شامل ڪرڻ جي ضرورت آهي ته جيئن اسين ٻيهر ڪرنسي مان نڪري سگهون.

Recursion ۾ Stack Overflow Error

اسان کي خبر آهي ته جڏهن ڪنهن به طريقي يا فنڪشن کي سڏيو ويندو آهي ته، فنڪشن جي حالت اسٽيڪ تي محفوظ ڪئي ويندي آهي ۽ حاصل ڪئي ويندي آهي جڏهن فنڪشن واپس اچي. اسٽيڪ کي استعمال ڪيو ويندو آهي ريٽرننگ ميٿڊ لاءِ پڻ.

پر ڪرنسي جي صورت ۾، هڪ مسئلو ٿي سگهي ٿو جيڪڏهن اسان بنيادي حالت جي وضاحت نه ڪريون يا جڏهن بنيادي حالت ڪنهن به طريقي سان پهچي يا عمل ۾ نه اچي. جيڪڏهن اها صورتحال ٿئي ٿي ته پوءِ اسٽيڪ اوور فلو ٿي سگهي ٿو.

اچو ته هيٺ ڏنل مثال تي غور ڪريون فڪري نوٽيشن.

هتي اسان غلط بنيادي شرط ڏني آهي، 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. انهي صورت ۾، اهو طريقو ڪڏهن به بنيادي حالت تي عمل نه ڪندو ۽ نتيجي ۾ اسٽيڪ اوور فلو ٿيندو.

جاوا ۾ Recursion Examples

هن سيڪشن ۾، اسان هيٺ ڏنل مثالن کي استعمال ڪندي لاڳو ڪنداسين. recursion.

#1) Fibonacci Series Using Recursion

فبونيڪي سيريز پاران ڏنل آهي،

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) چيڪ ڪريو ته ڇا نمبر ھڪڙو پيلينڊروم آھي Recursion استعمال ڪندي

palindrome ھڪڙو تسلسل آھي جيڪو برابر آھي جڏھن اسان ان کي کاٻي کان ساڄي يا ساڄي کان کاٻي طرف پڙهو.

هڪ نمبر 121 ڏنو ويو آهي، اسان ڏسون ٿا ته جڏهن اسين ان کي کاٻي کان ساڄي ۽ ساڄي کان کاٻي پڙهي سگهون ٿا، اهو برابر آهي. ان ڪري نمبر 121 هڪ پيلنڊروم آهي.

اچو هڪ ٻيو نمبر وٺون ٿا، 1242. جڏهن اسان ان کي کاٻي کان ساڄي پڙهون ٿا ته اهو 1242 آهي ۽ جڏهن ساڄي کان کاٻي طرف پڙهون ٿا ته اهو 2421 آهي. اهڙيءَ طرح هي پيلنڊروم نه آهي.

اسانانگن جي انگن کي ريورس ڪندي palindrome پروگرام کي لاڳو ڪريو ۽ ڏنل نمبر کي ان جي پٺتي پيل نمائندگي سان ڀيٽيو.

هيٺ ڏنل پروگرام پلينڊروم کي چيڪ ڪرڻ لاءِ پروگرام لاڳو ڪري ٿو.

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) ريورس اسٽرنگ ريڪرشن جاوا

هڪ اسٽرنگ ”هيلو“ ڏنو ته اسان کي ان کي ريورس ڪرڻو پوندو ته جيئن نتيجو وارو اسٽرنگ ”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); } }

Output

#4) Binary Search Java Recursion

A binary search algorithm is a famous algorithm for searching. هن الورورٿم ۾، 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 استعمال ڪندي Array ۾ گھٽ ۾ گھٽ قدر ڳولھيو

ٻيهر استعمال ڪندي اسين صف ۾ گھٽ ۾ گھٽ قدر پڻ ڳولي سگھون ٿا.

جيجاوا پروگرام ھيٺ ڏنل آھي گھٽ ۾ گھٽ قدر معلوم ڪرڻ لاءِ ايري ۾.

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"); } }

Output

22>

اھڙا ڪجھ آھن تکرار جا مثال. انهن مثالن کان سواءِ، سافٽ ويئر ۾ ٻيا به ڪافي مسئلا ريڪرسيو ٽيڪنڪ استعمال ڪري سگھجن ٿا.

Recursion Types

Recursion ٻن قسمن جو هوندو آهي ان بنياد تي جڏهن ڪال ڪئي ويندي آهي. recursive method.

اهي آهن:

#1) Tail Recursion

جڏهن ٻيهر ورجائڻ واري طريقي کي ڪال آخري بيان آهي recursive طريقي جي اندر تي عمل ڪيو وڃي ٿو، ان کي سڏيو ويندو آهي “Tail Recursion”.

tail recursion ۾، recursive call Statement عام طور تي طريقي جي واپسي واري بيان سان گڏ ڪيو ويندو آهي.

The tail recursion لاءِ عام نحو ھيٺ ڏنل آھي:

methodName ( T parameters…){ { if (base_condition == true) { return result; } return methodName (T parameters …) //tail recursion }

#2) Head Recursion

Head Recursion ڪنھن به ھر رڪشي وارو طريقو آھي جيڪو tail recursion نه آھي. تنهن ڪري عام ورهاڱي به اڳواٽ ريڪرشن آهي.

هيڊ ريڪرشن جو نحو هن ريت آهي:

methodName (T parameters…){ if (some_condition == true) { return methodName (T parameters…); } return result; }

جاوا ۾ ريٽرن بمقابله تکرار

Recursion	Iteration
Recursion ھڪڙو عمل آھي جتي ھڪڙو طريقو پاڻ کي بار بار سڏيندو آھي جيستائين بنيادي شرط پورا نه ٿي وڃي.	تڪرار آھي هڪ عمل جنهن جي ذريعي ڪوڊ جو هڪ ٽڪرو بار بار هڪ محدود تعداد لاءِ يا جيستائين هڪ شرط پوري نه ٿئي. لوپس لاءِ.
وڏي ڪوڊ جي سائيز لاءِ سٺو ڪم ڪري ٿو.
وڌيڪ ميموري استعمال ڪري ٿو جيئن هر بار بار واري ڪال کي اسٽيڪ ڏانهن ڌڪيو ويندو آهي	مقابلي طور تي گهٽ ميموري استعمال ڪيو ويندو آهي.
ڊبگ ڪرڻ ۽ برقرار رکڻ ۾ مشڪل	ڊيبگ ڪرڻ ۽ برقرار رکڻ آسان
اسٽيڪ اوور فلو ۾ نتيجا جيڪڏهن بنياد حالت بيان نه ڪئي وئي آهي يا نه پهچي وئي آهي.	شايد لامحدود طور تي عمل ڪري سگھي ٿو پر آخرڪار ڪنهن به ميموري غلطي سان عمل کي روڪي ڇڏيندو
وقت جي پيچيدگي تمام گهڻي آهي.	وقت جي پيچيدگي نسبتا هيٺين طرف آهي.

اڪثر پڇيا ويندڙ سوال

س #1) جاوا ۾ ريڪرشن ڪيئن ڪم ڪندو آهي؟

جواب: ورهاڱي ۾، ريسرسيو فنڪشن پاڻ کي بار بار سڏيندو آهي جيستائين بنيادي حالت مطمئن نه ٿئي. ڪالنگ فنڪشن لاءِ ميموري کي ڪالنگ فنڪشن لاءِ ميموري جي چوٽي تي اسٽيڪ تي ڌڪيو ويندو آهي. هر فنڪشن ڪال لاءِ، مقامي متغيرن جي الڳ ڪاپي ڪئي ويندي آهي.

Q #2) Recursion ڇو استعمال ڪيو ويندو آهي؟

جواب: Recursion استعمال ڪيو ويندو آهي انهن مسئلن کي حل ڪرڻ لاءِ جن کي ننڍن ۾ ورهائي سگهجي ٿو ۽ پوري مسئلي کي ننڍڙن مسئلن جي صورت ۾ بيان ڪري سگهجي ٿو.

Recursion انهن مسئلن لاءِ پڻ استعمال ڪيو ويندو آهي جيڪي تمام گهڻيون آهن. پيچيدگي کي ٻيهر استعمال ڪندي حل ڪيو وڃي. مسئلن کان علاوه جن لاءِ وقت جي پيچيدگي ڪو مسئلو ناهي، استعمال ڪريو ريٽرنشن.

س #3) ڇا فائدا آهنRecursion؟

جواب:

Recursion جا فائدا شامل آهن:

Recursion بيڪار ڪالنگ کي گھٽائي ٿو فنڪشن جو.
Recursion اسان کي آساني سان مسئلن کي حل ڪرڻ جي اجازت ڏئي ٿو جڏهن تکراري طريقي جي مقابلي ۾.

س # 4) ڪهڙو بهتر آهي - Recursion يا Iteration؟

جواب: Recursion بار بار ڪال ڪري ٿو جيستائين بنيادي فنڪشن پهچي وڃي. اهڙيءَ طرح اتي هڪ ميموري اوور هيڊ هوندي آهي جيئن هر فنڪشن ڪال لاءِ ميموري کي اسٽيڪ ڏانهن ڌڪيو ويندو آهي.

ٻي طرف ٻيهر ميموري اوور هيڊ نه هوندي آهي. ورهاڱي جي عمل کي ٻيهر ورجائڻ واري طريقي جي ڀيٽ ۾ سست آهي. Recursion ڪوڊ جي سائيز کي گھٽائي ٿو، جڏهن ته تکراري اپروچ ڪوڊ کي وڏو بڻائي ٿو.

Q #5) ٻيهر ٻيهر ورجائي جا فائدا ڇا آهن؟

جواب:

Recursion ڪوڊ کي صاف ۽ ننڍو بڻائي ٿو.
Recursion مسئلن لاءِ بار بار واري طريقي کان بهتر آهي جهڙوڪ ٽاور آف هانوئي، وڻ ٽريورسلز وغيره.
جيئن ته هر فنڪشن ڪال ميموري کي اسٽيڪ ڏانهن ڌڪيندي آهي، ريڪرشن وڌيڪ ميموري استعمال ڪندو آهي.
ريڪرشن ڪارڪردگي ٻيهر ٿيندڙ طريقي کان سست آهي.

نتيجو

سافٽ ويئر ۾ Recursion هڪ تمام اهم تصور آهي بغير ڪنهن پروگرامنگ جي ٻولي. Recursion گهڻو ڪري ڊيٽا جي ڍانچي جي مسئلن کي حل ڪرڻ ۾ استعمال ڪيو ويندو آهي جهڙوڪ ٽاورز آف هانوئي، وڻن جا ٽڪرا، ڳنڍيل فهرستون، وغيره. جيتوڻيڪ اهو وڌيڪ ياداشت وٺندو آهي،recursion ڪوڊ کي وڌيڪ آسان ۽ صاف بڻائي ٿو.

اسان هن سبق ۾ Recursion بابت سڀ ڪجهه ڄاڻايو آهي. تصور جي بهتر سمجھڻ لاءِ اسان ڪيترائي پروگرامنگ مثال پڻ لاڳو ڪيا آھن.