recursion : Java Glossary

recursion

In Java, a method may call itself. This is called recursion. You do not need to make any special declarations to make this possible. The trick is used mainly in exercises given in computer science class. In the real world, recursion has a bad name because you can overflow the stack if you are call yourself too many times without returning. If you recurse too deeply you will get a StackOverFlowError. Further, most cute recursive algorithms can be specified more efficiently with loops. The classic practical recursive algorithm is QuickSort. The classic student problem is to calculate n! with or without recursion.

Sometimes, recursion is indirect. Method a calls method b which in turn calls method a which in turn calls b.

Sometimes, you accidentally use recursion when you insert a call to the old method a in an overridden method a, and forget to say super. a();

Recursion to Descend A Directory Tree

Here is how you would delete all the files in the directory tree using recursion.

Fibonacci Recursion

The usual way to apply recursion is to divide a maxi-problem into two or more mini-problems, solve the minis, and combine their solutions to find the answer to the maxi-problem. The recursive aspect means that you apply the same technique to solve the mini-problems: Split them into micro-problems, solve the micros, and combine their solutions to solve the minis. And the micro-problems split into nano-problems, and so on. As the levels descend you eventually arrive at problems that are so small they can be solved by some other means (this is sometimes called the ground case).
Each small problem’s solution is passed back to the recursive step that asked for it, where it gets combined with the solutions of other small problems to solve the larger problem.
~ Eric Sosman

factorial
QuickSort
stack
tail recursion
yak shaving

	You can get the freshest copy of this page from:	or possibly from your local J: drive (Java virtual drive/mindprod.com website mirror)
	http://mindprod.com/jgloss/recursion.html	J:\mindprod\jgloss\recursion.html
	Please email your feedback for publication, letters to the editor, errors, omissions, typos, formatting errors, ambiguities, unclear wording, broken/redirected link reports, suggestions to improve this page or comments to Roedy Green : . If you want your message, your name or email kept confidential, not considered for public posting, please explicitly specify that. Unless you state otherwise, I will treat your message as a letter to the editor that I may or may not publish in the feedback section. After that, it will be too late to retract it. If you disagree with something I said, please quote it and cite the web page where you found it, tell me why you think it is wrong, and, if possible, provide some supporting evidence. Threatening to kill me or spouting obscenities has yet to persuade me to change my mind.
	Canadian Mind Products
	mindprod.com IP:[65.110.21.43]
view Blog	Your face IP:[38.107.179.211]
Feedback	You are visitor number 23,644.