## 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 intfactorial(intn) {

if(n == 0)return1;

returnn * 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.