Recursion

A recursive definition is definition that is defined in terms of itself. Here is an example from English grammar:

A noun-phrase is either
(1) a noun or
(2) an adjective followed by a noun-phrase.

Using that definition, these are all noun-phrases:

dog, big dog, big white dog, big white furry dog, big big big white dog.

Recursive definitions abound in mathematics. Think, for example of the definition of n! = n*(n-1)*...*1:

0! = 1
n! = n*(n-1)! for n > 0.

In programming, a recursive method is a method that contains a call on itself. It is easy to translate the above definition of n! into a recursive Java function:

/** Return n!
   * Precondition: n >= 0 */
public static int factorial(int n) {
    if (n == 0) return 1;
    return n * factorial(n-1);
}

How recursive calls are executed

You may wonder how recursive calls are executed. Once you understand how any call, nonrecursive or recursive, is executed, any confusion will disappear. These videos explain execution of method calls.

How to understand that a recursive method implements its specification

Understanding a recursive method:base cases and recursive cases: pdf file.
Using a bound function to prove termination of recursion: pdf file.

Developing recursive methods

Developing a recursive function: pdf file.
Developing a recursive function to add up the integers in an array of any number of dimensions: pdf file.
Recursion may require extra parameters: pdf file.
Tail calls and how to optimize them. pdf file.

Using recursion to reverse a singly linked list

A surprisingly simple method easily arises by using assertions to keep track of what has been done and what remains to be done: webpage.

Using recursion to traverse trees

Two models for using recursion for traversing trees: webpage.

Recursion on binary trees: second page of pdf file.

Developing a recursive function to determine whether a binary tree is a BST: pdf file.
( It uses the Mañana Principle, which you might want to glance at in this pdf file.)

Using recursion to traverse graphs

The simplest depth-first search of a graph is recursive. Watch the first two videos on this page.