Next: Towers of Hanoi. Up: Recursion. Previous: None.

**Recursion** is the concept of something being defined
in terms of itself. It sounds like it's circular - but it's not
necessarily so. A circular definition, like defining a rose as a rose,
is termed **infinite recursion**. But some recursive
definitions aren't circular: They have a **base case**,
where the recursive definition no longer applies, and the definition for
any other case eventually reaches the base case.

In mathematics, things are often defined recursively. For example,
the Fibonacci numbers are often defined recursively. The
**Fibonacci** numbers are defined as the sequence beginning
with two 1's, and where each succeeding number in the sequence is the
sum of the two preceeding numbers.

We obtained 8 in the above sequence by summing the previous two numbers (3 and 5).1 1 2 3 5 8 13 21 34 55 ...

A formal mathematical definition would define this using mathematical symbols.

This makes the recursiveness of the definition obvious: Notice how we've defined F(n) in terms of F (namely, F(n-1) + F(n-2)). (Incidentally, such recursive definitions of functions are called1 if n = 0 or n = 1 F(n) = { F(n-1) + F(n-2) otherwise

In computer programming, also, it's often convenient to define something recursively. And Java allows you to do this - all you have to do is to use the function within its own definition. The following program computes and prints a Fibonacci number requested by the user.

import csbsju.cs160.*; public class Fibonacci { public static void main(String[] args) { IO.println("Which Fibonacci? "); IO.println("It is " + fib(IO.readInt())); } private static int fib(int n) { if(n <= 1) return 1; else return fib(n - 1) + fib(n - 2); } }

Notice how the recursive function has its base case - in this
example, the base case is when `n` is at most 1, when the program
returns 1 without any further recursive calls. *Recursive
programs must always have a base case!* Novices tend to forget to
include a base case when programming.

As a programmer, it's important that you understand how this works
within the computer. The computer will go through the following process
to compute `fib(3)`:

3 exceeds 1, so I need to compute and return fib(3 - 1) + fib(3 - 2). To compute this, I first need to compute fib(2). 2 exceeds 1, so I need to compute and return fib(2 - 1) + fib(2 - 2). To compute this, I first need to compute fib(1). 1 is less than or equal to 1, so I need to return 1. Now that I know fib(1), I need to compute fib(0). 0 is less than or equal to 1, so I need to return 1. I now know fib(2 - 1) + fib(2 - 2) = 1 + 1 = 2. I return this. Now that I know fib(2) is 2, I need to compute fib(1). 1 is less than or equal to 1, so I need to return 1. I now know fib(3 - 1) + fib(3 - 2) = 2 + 1 = 3. I return this.

It helps to draw a **recursion tree** to illustrate the
different recursive calls entered in the process of the computation.
A recursion tree has a node for each call of the method, connected by a
line to the method call that called it. For the example of
`fib(3)`, the recursion tree would be as follows.

Next: Towers of Hanoi. Up: Recursion. Previous: None.