Java Tutorial/Class Definition/Recursive Method
Версия от 17:44, 31 мая 2010; (обсуждение)
Содержание
Recursion: a method (function) calls itself
Characteristics of Recursive Methods:
- Method calls itself.
- When it calls itself, it solves a smaller problem.
- There is a smallest problem that the routine can solve it, and return, without calling itself.
public class MainClass {
public static void main(String[] args) {
int theAnswer = triangle(12);
System.out.println("Triangle=" + theAnswer);
}
public static int triangle(int n) {
if (n == 1)
return 1;
else
return (n + triangle(n - 1));
}
}
Triangle=78
Recursion: another example
public class MainClass {
public static void main(String[] args) {
double x = 5.0;
System.out.println(x + " to the power 4 is " + power(x, 4));
System.out.println("7.5 to the power 5 is " + power(7.5, 5));
System.out.println("7.5 to the power 0 is " + power(7.5, 0));
System.out.println("10 to the power -2 is " + power(10, -2));
}
// Raise x to the power n
static double power(double x, int n) {
if (n > 1)
return x * power(x, n - 1); // Recursive call
else if (n < 0)
return 1.0 / power(x, -n); // Negative power of x
else
return x;
}
}
5.0 to the power 4 is 625.0 7.5 to the power 5 is 23730.46875 7.5 to the power 0 is 7.5 10 to the power -2 is 0.01
Recursive factorial method
public class MainClass {
public static void main(String args[]) {
for (int counter = 0; counter <= 10; counter++)
System.out.printf("%d! = %d\n", counter, factorial(counter));
}
// recursive declaration of method factorial
public static long factorial(long number) {
if (number <= 1) // test for base case
return 1; // base cases: 0! = 1 and 1! = 1
else
// recursion step
return number * factorial(number - 1);
}
}
0! = 1 1! = 1 2! = 2 3! = 6 4! = 24 5! = 120 6! = 720 7! = 5040 8! = 40320 9! = 362880 10! = 3628800
Recursive fibonacci method
public class MainClass {
// recursive declaration of method fibonacci
public static long fibonacci(long number) {
if ((number == 0) || (number == 1)) // base cases
return number;
else
// recursion step
return fibonacci(number - 1) + fibonacci(number - 2);
}
public static void main(String[] args) {
for (int counter = 0; counter <= 10; counter++)
System.out.printf("Fibonacci of %d is: %d\n", counter, fibonacci(counter));
}
}
Fibonacci of 0 is: 0 Fibonacci of 1 is: 1 Fibonacci of 2 is: 1 Fibonacci of 3 is: 2 Fibonacci of 4 is: 3 Fibonacci of 5 is: 5 Fibonacci of 6 is: 8 Fibonacci of 7 is: 13 Fibonacci of 8 is: 21 Fibonacci of 9 is: 34 Fibonacci of 10 is: 55
Recursive method to find all permutations of a String
public class MainClass {
public static void main(String args[]) {
permuteString("", "String");
}
public static void permuteString(String beginningString, String endingString) {
if (endingString.length() <= 1)
System.out.println(beginningString + endingString);
else
for (int i = 0; i < endingString.length(); i++) {
try {
String newString = endingString.substring(0, i) + endingString.substring(i + 1);
permuteString(beginningString + endingString.charAt(i), newString);
} catch (StringIndexOutOfBoundsException exception) {
exception.printStackTrace();
}
}
}
}
String Strign Strnig Strngi Strgin Strgni Stirng Stirgn Stinrg Stingr Stigrn Stignr Stnrig Stnrgi Stnirg Stnigr Stngri Stngir Stgrin Stgrni Stgirn Stginr Stgnri Stgnir Srting Srtign Srtnig Srtngi Srtgin Srtgni Sritng Sritgn Srintg Sringt Srigtn Srignt Srntig Srntgi Srnitg Srnigt Srngti Srngit Srgtin Srgtni Srgitn Srgint Srgnti Srgnit Sitrng Sitrgn Sitnrg Sitngr Sitgrn Sitgnr Sirtng Sirtgn Sirntg Sirngt Sirgtn Sirgnt Sintrg Sintgr Sinrtg Sinrgt Singtr Singrt Sigtrn Sigtnr Sigrtn Sigrnt Signtr Signrt Sntrig Sntrgi Sntirg Sntigr Sntgri Sntgir Snrtig Snrtgi Snritg Snrigt Snrgti Snrgit Snitrg Snitgr Snirtg Snirgt Snigtr Snigrt Sngtri Sngtir Sngrti Sngrit Sngitr Sngirt Sgtrin Sgtrni Sgtirn Sgtinr Sgtnri Sgtnir Sgrtin Sgrtni Sgritn Sgrint Sgrnti Sgrnit Sgitrn Sgitnr Sgirtn Sgirnt Sgintr Sginrt Sgntri Sgntir Sgnrti Sgnrit Sgnitr Sgnirt tSring tSrign tSrnig tSrngi tSrgin tSrgni tSirng tSirgn tSinrg tSingr tSigrn tSignr tSnrig tSnrgi tSnirg tSnigr tSngri tSngir tSgrin tSgrni tSgirn tSginr tSgnri tSgnir trSing trSign trSnig trSngi trSgin trSgni triSng triSgn trinSg tringS trigSn trignS trnSig trnSgi trniSg trnigS trngSi trngiS trgSin trgSni trgiSn trginS trgnSi trgniS tiSrng tiSrgn tiSnrg tiSngr tiSgrn tiSgnr tirSng tirSgn tirnSg tirngS tirgSn tirgnS tinSrg tinSgr tinrSg tinrgS tingSr tingrS tigSrn tigSnr tigrSn tigrnS tignSr tignrS tnSrig tnSrgi tnSirg tnSigr tnSgri tnSgir tnrSig tnrSgi tnriSg tnrigS tnrgSi tnrgiS tniSrg tniSgr tnirSg tnirgS tnigSr tnigrS tngSri tngSir tngrSi tngriS tngiSr tngirS tgSrin tgSrni tgSirn tgSinr tgSnri tgSnir tgrSin tgrSni tgriSn tgrinS tgrnSi tgrniS tgiSrn tgiSnr tgirSn tgirnS tginSr tginrS tgnSri tgnSir tgnrSi tgnriS tgniSr tgnirS rSting rStign rStnig rStngi rStgin rStgni rSitng rSitgn rSintg rSingt rSigtn rSignt rSntig rSntgi rSnitg rSnigt rSngti rSngit rSgtin rSgtni rSgitn rSgint rSgnti rSgnit rtSing rtSign rtSnig rtSngi rtSgin rtSgni rtiSng rtiSgn rtinSg rtingS rtigSn rtignS rtnSig rtnSgi rtniSg rtnigS rtngSi rtngiS rtgSin rtgSni rtgiSn rtginS rtgnSi rtgniS riStng riStgn riSntg riSngt riSgtn riSgnt ritSng ritSgn ritnSg ritngS ritgSn ritgnS rinStg rinSgt rintSg rintgS ringSt ringtS rigStn rigSnt rigtSn rigtnS rignSt rigntS rnStig rnStgi rnSitg rnSigt rnSgti rnSgit rntSig rntSgi rntiSg rntigS rntgSi rntgiS rniStg rniSgt rnitSg rnitgS rnigSt rnigtS rngSti rngSit rngtSi rngtiS rngiSt rngitS rgStin rgStni rgSitn rgSint rgSnti rgSnit rgtSin rgtSni rgtiSn rgtinS rgtnSi rgtniS rgiStn rgiSnt rgitSn rgitnS rginSt rgintS rgnSti rgnSit rgntSi rgntiS rgniSt rgnitS iStrng iStrgn iStnrg iStngr iStgrn iStgnr iSrtng iSrtgn iSrntg iSrngt iSrgtn iSrgnt iSntrg iSntgr iSnrtg iSnrgt iSngtr iSngrt iSgtrn iSgtnr iSgrtn iSgrnt iSgntr iSgnrt itSrng itSrgn itSnrg itSngr itSgrn itSgnr itrSng itrSgn itrnSg itrngS itrgSn itrgnS itnSrg itnSgr itnrSg itnrgS itngSr itngrS itgSrn itgSnr itgrSn itgrnS itgnSr itgnrS irStng irStgn irSntg irSngt irSgtn irSgnt irtSng irtSgn irtnSg irtngS irtgSn irtgnS irnStg irnSgt irntSg irntgS irngSt irngtS irgStn irgSnt irgtSn irgtnS irgnSt irgntS inStrg inStgr inSrtg inSrgt inSgtr inSgrt intSrg intSgr intrSg intrgS intgSr intgrS inrStg inrSgt inrtSg inrtgS inrgSt inrgtS ingStr ingSrt ingtSr ingtrS ingrSt ingrtS igStrn igStnr igSrtn igSrnt igSntr igSnrt igtSrn igtSnr igtrSn igtrnS igtnSr igtnrS igrStn igrSnt igrtSn igrtnS igrnSt igrntS ignStr ignSrt igntSr igntrS ignrSt ignrtS nStrig nStrgi nStirg nStigr nStgri nStgir nSrtig nSrtgi nSritg nSrigt nSrgti nSrgit nSitrg nSitgr nSirtg nSirgt nSigtr nSigrt nSgtri nSgtir nSgrti nSgrit nSgitr nSgirt ntSrig ntSrgi ntSirg ntSigr ntSgri ntSgir ntrSig ntrSgi ntriSg ntrigS ntrgSi ntrgiS ntiSrg ntiSgr ntirSg ntirgS ntigSr ntigrS ntgSri ntgSir ntgrSi ntgriS ntgiSr ntgirS nrStig nrStgi nrSitg nrSigt nrSgti nrSgit nrtSig nrtSgi nrtiSg nrtigS nrtgSi nrtgiS nriStg nriSgt nritSg nritgS nrigSt nrigtS nrgSti nrgSit nrgtSi nrgtiS nrgiSt nrgitS niStrg niStgr niSrtg niSrgt niSgtr niSgrt nitSrg nitSgr nitrSg nitrgS nitgSr nitgrS nirStg nirSgt nirtSg nirtgS nirgSt nirgtS nigStr nigSrt nigtSr nigtrS nigrSt nigrtS ngStri ngStir ngSrti ngSrit ngSitr ngSirt ngtSri ngtSir ngtrSi ngtriS ngtiSr ngtirS ngrSti ngrSit ngrtSi ngrtiS ngriSt ngritS ngiStr ngiSrt ngitSr ngitrS ngirSt ngirtS gStrin gStrni gStirn gStinr gStnri gStnir gSrtin gSrtni gSritn gSrint gSrnti gSrnit gSitrn gSitnr gSirtn gSirnt gSintr gSinrt gSntri gSntir gSnrti gSnrit gSnitr gSnirt gtSrin gtSrni gtSirn gtSinr gtSnri gtSnir gtrSin gtrSni gtriSn gtrinS gtrnSi gtrniS gtiSrn gtiSnr gtirSn gtirnS gtinSr gtinrS gtnSri gtnSir gtnrSi gtnriS gtniSr gtnirS grStin grStni grSitn grSint grSnti grSnit grtSin grtSni grtiSn grtinS grtnSi grtniS griStn griSnt gritSn gritnS grinSt grintS grnSti grnSit grntSi grntiS grniSt grnitS giStrn giStnr giSrtn giSrnt giSntr giSnrt gitSrn gitSnr gitrSn gitrnS gitnSr gitnrS girStn girSnt girtSn girtnS girnSt girntS ginStr ginSrt gintSr gintrS ginrSt ginrtS gnStri gnStir gnSrti gnSrit gnSitr gnSirt gntSri gntSir gntrSi gntriS gntiSr gntirS gnrSti gnrSit gnrtSi gnrtiS gnriSt gnritS gniStr gniSrt gnitSr gnitrS gnirSt gnirtS
The Towers of Hanoi
public class MainClass {
public static void main(String[] args) {
int nDisks = 3;
doTowers(nDisks, "A", "B", "C");
}
public static void doTowers(int topN, char from, char inter, char to) {
if (topN == 1){
System.out.println("Disk 1 from " + from + " to " + to);
}else {
doTowers(topN - 1, from, to, inter);
System.out.println("Disk " + topN + " from " + from + " to " + to);
doTowers(topN - 1, inter, from, to);
}
}
}
Disk 1 from A to C Disk 2 from A to B Disk 1 from C to B Disk 3 from A to C Disk 1 from B to A Disk 2 from B to C Disk 1 from A to C
