Ĉi tiu Detala Lernilo pri Rikurso en Java Klarigas kio estas Rikuro kun Ekzemploj, Tipoj kaj Rilataj Konceptoj. Ĝi ankaŭ kovras Rekursion Vs Iteracion:
De niaj pli fruaj lerniloj en Java, ni vidis la ripetan aliron en kiu ni deklaras buklon kaj poste trairas datumstrukturon en ripeta maniero prenante unu elementon ĉe fojon.
Ni ankaŭ vidis la kondiĉan fluon kie denove ni konservas unu buklan variablon kaj ripetas kodon ĝis la cirkla variablo plenumas la kondiĉon. Kiam temas pri funkciovokoj, ni esploris la ripetan aliron ankaŭ por funkciovokoj.
Kio Estas Rekursio en Java?
Rekurso estas procezo per kiu funkcio aŭ metodo ree kaj denove nomas sin. Ĉi tiu funkcio, kiu estas ree kaj ree vokita aŭ rekte aŭ nerekte, estas nomata "rekursiva funkcio".
Ni vidos diversajn ekzemplojn por kompreni rekurson. Nun ni vidu la sintakson de rikurso.
Rekursa sintakso
Ajna metodo, kiu efektivigas Rikurson, havas du bazajn partojn:
- Metodovoko kiu povas nomi sin t.e. rekursiva
- Antaŭkondiĉo kiu ĉesigos la rekursion.
Rimarku ke antaŭkondiĉo estas necesa por iu ajn rekursiva metodo kiel, se ni ne faras rompi larikurso tiam ĝi daŭre funkcios senfine kaj rezultigos stakan superfluon.
La ĝenerala sintakso de rikurso estas jena:
methodName (T parameters…) { if (precondition == true) //precondition or base condition { return result; } return methodName (T parameters…); //recursive call } Rimarku, ke la antaŭkondiĉo ankaŭ nomiĝas baza kondiĉo. Ni diskutos pli pri la baza kondiĉo en la sekva sekcio.
Kompreni Rikurson En Java
En ĉi tiu sekcio, ni provos kompreni la rekursan procezon kaj vidos kiel ĝi okazas. Ni lernos pri la baza kondiĉo, staka superfluo, kaj vidos kiel aparta problemo povas esti solvita per rekursio kaj aliaj tiaj detaloj.
Rekursia Baza Kondiĉo
Dum la verkado de la rekursiva programo, ni devus unue provizu la solvon por la baza kazo. Tiam ni esprimas la pli grandan problemon en terminoj de pli malgrandaj problemoj.
Kiel ekzemplo, ni povas preni klasikan problemon pri kalkulo de la faktorialo de nombro. Donita nombron n, ni devas trovi faktorialon de n indikita per n!
Nun ni efektivigu la programon por kalkuli la n faktorialon (n!) uzante rekursion.
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); } }Eligo
En ĉi tiu programo, ni povas vidi ke la kondiĉo (n=1) estas la baza kondiĉo kaj kiam ĉi tiu kondiĉo estas atingita, la funkcio liveras 1 La alia parto de la funkcio estas la rekursiva alvoko. Sed ĉiufoje kiam la rekursiva metodo estas vokita, n malpliiĝas je 1.
Tiele ni povas konkludi, ke finfine la valoro de n fariĝos 1 aŭ malpli ol 1 kaj ĉe ĉi tiopunkto, la metodo redonos valoron 1. Ĉi tiu baza kondiĉo estos atingita kaj la funkcio ĉesos. Rimarku, ke la valoro de n povas esti io ajn, kondiĉe ke ĝi kontentigas la bazan kondiĉon.
Problemo-Solvado Uzante Rekursio
La baza ideo malantaŭ uzado de Rikurso estas esprimi la pli grandan problemon laŭ terminoj de pli malgrandaj problemoj. Ankaŭ, ni devas aldoni unu aŭ plurajn bazajn kondiĉojn por ke ni povu eliri el rekurso.
Ĉi tio jam estis pruvita en la supra faktoria ekzemplo. En ĉi tiu programo, ni esprimis la n faktorialon (n!) laŭ pli malgrandaj valoroj kaj havis bazan kondiĉon (n =1) tiel ke kiam n atingas 1, ni povas forlasi la rekursivan metodon.
Stack Overflow Error In Recursion
Ni konscias, ke kiam iu ajn metodo aŭ funkcio estas vokita, la stato de la funkcio estas konservita sur la stako kaj estas retrovita kiam la funkcio revenas. La stako estas uzata ankaŭ por la rekursiva metodo.
Sed en la kazo de rekurso, problemo povus okazi se ni ne difinas la bazan kondiĉon aŭ kiam la baza kondiĉo estas iel ne atingita aŭ efektivigita. Se ĉi tiu situacio okazas tiam la staka superfluo povas ekesti.
Ni konsideru la malsupran ekzemplon de faktoria skribmaniero.
Ĉi tie ni donis malĝustan bazan kondiĉon, 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); } }Do kiam n > 100 la metodo revenos 1 sed rekurso ne ĉesos. La valoro de n daŭre malpliiĝos senfine kiel tiene estas alia kondiĉo por haltigi ĝin. Ĉi tio daŭros ĝis stako superfluas.
Alia kazo estos kiam la valoro de n 100. En ĉi tiu kazo, ankaŭ la metodo neniam ekzekutos la bazan kondiĉon kaj rezultigos stakan superfluon.
Ekzemploj de Rikurso En Java
En ĉi tiu sekcio, ni efektivigos la sekvajn ekzemplojn uzante rekurso.
#1) Fibonacci-Serio Uzanta Rekursion
La Fibonacci-serio estas donita per,
1,1,2,3,5,8,13,21, 34,55,...
La ĉi-supra sinsekvo montras, ke la nuna elemento estas la sumo de la antaŭaj du elementoj. Ankaŭ, la unua elemento en la serio de Fibonacci estas 1.
Do ĝenerale se n estas la nuna nombro, tiam ĝi estas donita per la sumo de (n-1) kaj (n-2). Ĉar la nuna elemento estas esprimita laŭ antaŭaj elementoj, ni povas esprimi ĉi tiun problemon uzante rekurson.
La programo por efektivigi la serion de Fibonacci estas donita sube:
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) + " "); } } } Eligo
#2) Kontrolu Ĉu Nombro Estas Palindromo Uzanta Rikurson
Palindromo estas sinsekvo kiu estas egala kiam ni legi ĝin de maldekstre dekstren aŭ dekstren maldekstren.
Donita numeron 121, oni vidas, ke kiam oni legas ĝin de maldekstre dekstren kaj dekstren maldekstren, ĝi estas egala. Tial numero 121 estas palindromo.
Ni prenu alian numeron, 1242. Kiam ni legas ĝin de maldekstre dekstren ĝi estas 1242 kaj kiam oni legas de dekstre maldekstre, ĝi legas kiel 2421. Tiel tio ne estas palindromo.
Niefektivigu la palindroman programon inversigante la ciferojn de nombroj kaj rekursie komparu la donitan nombron al ĝia inversa prezento.
La suba programo efektivigas la programon por kontroli la palindromon.
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."); } } }Eligo
#3) Reverse String Recursion Java
Donita ĉeno "Saluton" ni devas inversigi ĝin tiel ke la rezulta ĉeno estas “olleH”.
Ĉi tio estas farita per rekurso. Komencante de la lasta signo en la ĉeno ni rekursie presas ĉiun signon ĝis ĉiuj signoj en la ĉeno estas elĉerpitaj.
La suba programo uzas rekursion por inversigi donitan ĉenon.
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); } } Eligo
#4) Duuma Serĉa Java Rekursio
Duuma serĉalgoritmo estas fama algoritmo por serĉado. En ĉi tiu algoritmo, donita ordigita tabelo de n elementoj, ni serĉas ĉi tiun tabelon por la donita ŝlosila elemento. Komence, ni dividas la tabelon en du duonojn trovante la mezan elementon de la tabelo.
Tiam depende de ĉu la ŝlosilo meze ni limigas nian serĉon en la unua aŭ dua duono de la tabelo. Tiamaniere la sama procezo estas ripetita ĝis la loko de la ŝlosilaj elementoj estas trovita.
Ni efektivigos ĉi tiun algoritmon uzante rekurson ĉi tie.
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); } } Eligo
#5) Trovu Minimuman Valoron En Tabelo Uzante Rekursion
Uzante rekurson ni ankaŭ povas trovi la minimuman valoron en la tabelo. 0> LaJava programo por trovi la minimuman valoron en la tabelo estas donita sube.
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"); } }Eligo
Ĉi tiuj estas kelkaj el la ekzemploj de rekurso. Krom ĉi tiuj ekzemploj, multaj aliaj problemoj en la programaro povas esti efektivigitaj uzante rekursivajn teknikojn.
Rikursaj tipoj
Rikurso estas de du tipoj bazitaj sur kiam la voko estas farita al la rekursiva metodo.
Ili estas:
#1) Tail Recursion
Kiam la voko al la rekursiva metodo estas la lasta aserto ekzekutita ene de la rekursiva metodo, ĝi nomiĝas "Tail Recursion".
En vosta rekursio, la rekursiva voka deklaro estas kutime ekzekutita kune kun la revena deklaro de la metodo.
La ĝenerala sintakso por vosta rikurso estas donita malsupre:
methodName ( T parameters…){ { if (base_condition == true) { return result; } return methodName (T parameters …) //tail recursion } #2) Kapa rikurso
Kapa rikurso estas ajna rekursia aliro kiu ne estas vosta rikurso. Do eĉ ĝenerala rekurso estas antaŭa rekurso.
Sintakso de kaprekurso estas jena:
methodName (T parameters…){ if (some_condition == true) { return methodName (T parameters…); } return result; } Rikuro kontraŭ ripeto en Java
| Rikuro | Iteracio |
|---|---|
| Rikuro estas procezo kie metodo vokas sin plurfoje ĝis baza kondiĉo estas plenumita. | Iteracio estas. procezo per kiu peco de kodo estas plurfoje efektivigita por finia nombro da fojoj aŭ ĝis kondiĉo estas plenumita. |
| Ĉu la aplikaĵo por funkcioj. | Ĉu aplikeblas. for loops. |
| Funkcias bone porpli malgranda koda grandeco. | Funkcias bone por pli granda koda grandeco. |
| Uzas pli da memoro ĉar ĉiu rekursiva voko estas puŝita al la stako | Kompare malpli da memoro. estas uzata. |
| Malfacile sencimigi kaj prizorgi | Pli facile sencimigi kaj prizorgi |
| Rezultoj en staksuperfluo se la bazo kondiĉo ne estas specifita aŭ ne atingita. | Eble efektiviĝos senfine sed finfine ĉesos ekzekuton kun iuj memoraj eraroj |
| Tempokomplekseco estas tre alta. | Tempokomplekseco estas relative en la malsupera flanko. |
Oftaj Demandoj
Q #1) Kiel Rekurso funkcias en Java?
Respondo: En rekursio, la rekursiva funkcio vokas sin plurfoje ĝis baza kondiĉo estas kontentigita. La memoro por la vokita funkcio estas puŝita al la stako ĉe la supro de la memoro por la voka funkcio. Por ĉiu funkciovoko, aparta kopio de lokaj variabloj estas farita.
Q #2) Kial estas uzata Rikuro?
Respondo: Rikuro estas uzata por solvi tiujn problemojn, kiuj povas esti dividitaj en pli malgrandajn kaj la tuta problemo povas esti esprimita en terminoj de pli malgranda problemo.
Rekurso estas uzata ankaŭ por tiuj problemoj, kiuj estas tro. komplekso solvi per ripeta aliro. Krom la problemoj por kiuj tempokomplekseco ne estas problemo, uzu rekursion.
Q #3) Kiuj estas la avantaĝoj deRikurso?
Respondo:
La avantaĝoj de Rikurso inkluzivas:
- Rekurso reduktas redundan vokon de funkcio.
- Rekurso ebligas al ni solvi problemojn facile kompare kun la ripeta aliro.
Q #4) Kiu estas pli bona – Rikuro aŭ Iteracio?
Respondo: Rikuro faras ripetajn vokojn ĝis la baza funkcio estas atingita. Tiel estas memoro superkosto ĉar memoro por ĉiu funkciovoko estas puŝita al la stako.
Iteracio aliflanke ne havas multe da memoro superkompeto. Rikur-ekzekuto estas pli malrapida ol la ripeta aliro. Rikuro reduktas la grandecon de la kodo dum la ripeta aliro faras la kodon granda.
Q #5) Kiuj estas la Avantaĝoj de Rikurso super Iteracio?
Respondo:
- Rikuro faras la kodon pli klara kaj pli mallonga.
- Rekurso estas pli bona ol la ripeta aliro por problemoj kiel la Turo de Hanojo, arbo. travojadoj, ktp.
- Ĉar ĉiu funkciovoko havas memoron puŝitan al la stako, Rekursio uzas pli da memoro.
- Rikurdefikeco estas pli malrapida ol la ripeta aliro.
Konkludo
Rekurso estas tre grava koncepto en programaro sendepende de la programlingvo. Rekurso estas plejparte uzata por solvi datumstrukturajn problemojn kiel turoj de Hanojo, trapasoj de arboj, ligitaj listoj, ktp. Kvankam ĝi bezonas pli da memoro,rikurso faras kodon pli simpla kaj pli klara.
Ni esploris ĉion pri Rikurso en ĉi tiu lernilo. Ni ankaŭ efektivigis multajn programajn ekzemplojn por pli bona kompreno de la koncepto.