Chapter 9.1 – Java Recursion | Introduction to Programming Using Java
9.1 Java Recursion
At one time or another, you’ve probably been told that you can’t define something in terms of itself. Nevertheless, if it’s done right, defining something at least partially in terms of itself can be a very powerful technique. A recursive definition is one that uses the concept or thing that is being defined as part of the definition.
For example: An “ancestor” is either a parent or an ancestor of a parent. A “sentence” can be, among other things, two sentences joined by a conjunction such as “and.” A “directory” is a part of a disk drive that can hold files and directories.
In mathematics, a “set” is a collection of elements, which can themselves be sets. A “statement” in Java can be a while statement, which is made up of the word “while”, a boolean-valued condition, and a statement.
Recursive definitions can describe very complex situations with just a few words. A definition of the term “ancestor” without using recursion might go something like “a parent, or a grandparent, or a great-grandparent, or a great-great-grandparent, and so on.”
But saying “and so on” is not very rigorous. (I’ve often thought that recursion is really just a rigorous way of saying “and so on.”) You run into the same problem if you try to define a “directory” as “a file that is a list of files, where some of the files can be lists of files, where some of those files can be lists of files, and so on.”
Trying to describe what a Java statement can look like, without using recursion in the definition, would be difficult and probably pretty comical.
Recursion can be used as a programming technique. A recursive subroutine is one that calls itself, either directly or indirectly. To say that a subroutine calls itself directly means that its definition contains a subroutine call statement that calls the subroutine that is being defined.
To say that a subroutine calls itself indirectly means that it calls a second subroutine which in turn calls the first subroutine (either directly or indirectly). A recursive subroutine can define a complex task in just a few lines of code.
In the rest of this section, we’ll look at a variety of examples, and we’ll see other examples in the rest of the book.
SEE MORE:
- Chapter 9.1.2 Towers of Hanoi | Introduction to Programming Using Java
- Chapter 9.3.1 Stacks | Introduction to Programming Using Java
- Chapter 9.4.1 Tree Traversal | Introduction to Program,ming Using Java
- Chapter 10.1.1 Generic Programming in Smalltalk | Introduc’tion to Programming Using Java
- Chapter 10.1.2 Generic Programming in C++ | Introduction to Program’ming Using Java
- Chapter 10.1.3 Generic Programming in Java | Introduction to Program,ming Using Java
- Chapter 10.1.4 The Java Collection Framework | Introduc’tion to Program’ming Using Java
- Chapter 10.1.5 Iterators and for-each Loops | Introduction to Programming Using Java
- Chapter 12 Advanced GUI Programming | Images and Resources | Introduction to Program ming Using Java
4 thoughts on “Chapter 9.1 – Java Recursion | Introduction to Programming Using Java”