Algorithms in Java, Third Edition, Parts 1-4: Fundamentals, Data Structures, Sorting, Searching

Chapter Five. Recursion and Trees

The concept of recursion is fundamental in mathematics and computer science. The simple definition is that a recursive program in a programming language is one that invokes itself (just as a recursive function in mathematics is one that is defined in terms of itself). A recursive program cannot invoke itself always, or it would never stop (just as a recursive function cannot be defined in terms of itself always, or the definition would be circular); so a second essential ingredient is that there must be a termination condition when the program can cease to invoke itself (and when the mathematical function is not defined in terms of itself). All practical computations can be couched in a recursive framework. ...