Recursion

(Note, text examples (page 51) use the Generic Computable interface defined on page 38)

Recursion is a general method of solving problems by reducing them to simpler problems of a similar type.

General Algorithm (problem solving tool) of Divide and Conquer

Postpone work

(if defined recursively (inductively), work is easy)

For a web-oriented example, consider designing a "web-crawler" that will search every hyperlink that is accessible from a specific page.

Pseudo-code (idea from Core Java)

Recursive_URL_search(link) Do find next_link Recursive_URL_search (next_link) Until No_more_links

Requirements

Three important aspects to always remember in code

When ... why recursion?

If problem itself is recursively defined

To describe a backtracking procedure

Provability of correctness (induction)

Ease of programming

Why not?

One can always take a recursive program and do it non-recursively.

Recursion Example

Problem: n factorial       n!

n! = n * (n-1) * (n-2) * ... * 1 0! = 1 1! = 1 2! = 2 * 1 = 2 3! = 3 * 2 * 1 = 6 ...

Iterative procedure: explicit repetition of some process until certain condition is met

public int fact(int n){ int x, prod; x = n; prod = 1; while (x != 0) { prod = x * prod; x --; } return prod; } But note:

recursive definition

(circular definition ...uses itself)

(e.g., 5! = 5 * 4!) ...

Recursive procedure

public int fact(int n){ int x, y; if (n ==0) { return 1;} // recursion must stop! else { x = n--; // decrement to get to halt y = n * fact(x); /* fact called on this (i.e., this.fact) (essential to recursion; must call self) */ return y; } } Even smaller text version in utilities.MyMath

public static int factorial(int n) { if (n <= 1) return 1; else return n * factorial(n - 1); }

For any recursive problem one needs to consider two features:

  1. Are solutions easy to give for special states (stop state)?
    (need to identify a "trivial" case)
  2. Given a state (not the stop state) are there clear rules for proceeding to a new state that is either
    1. a stop state
    2. leads to a stop state

I.e., find a method to solve the "complex" case in terms of a "simpler" case (the conquer is easier if divide)

Other Recursion Examples:

From text: Permutation.java with Fig1.11

Binary Search

In text, page 129 iterative, and recursive (Both use java.lang.Comparable)

Range: Finding Max and Min

For your lab, think carefully - you are doing a search for max and min, but the set is not ordered - so you will have to look at all. The divide part will be to break in half (like binary search). The conquer part will not be until you are at an element (i.e., a stop state for finding a max (or a min) is when there is only one element! If S = {a}, then the min is (a). If you have 2 parts then what? Note also that you may need to use a "driver" like the author did in recursiveSum().

Book Exercises: page 54 Try #24 (Fibonacci), 26 (Ackerman), 29 (PowerSet)

#24 Fibonacci
Define: F(1) = 1, F(2)= 1, then
In general F(n) = F(n-1) + F(n-2)

Examples

text code