Chapter 1: Recursion

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

Recursive_URL_search(link) repeat find next_link Recursive_URL_search (next_link) until No_more_links 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

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

recursive definition

(circular definition ...uses itself)

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

Recursive procedure

Algorithm fact(n){ if (n ==0) then return 1 // recursion must stop! else { x = n--; // decrement to get to halt y = n * fact(x); //essential to recursion-must call self return y; } }

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)

Exercises: Binary Search, Book page 13, # 5, 6, 7, 8, 12

Exercise 6: The Fibonacci numbers

From David Eppstein's lecture notes at UC Irvine here but don't freak out. We will not get that far into it.

An interesting problem for recursive algorithms is the computation of Fibonacci numbers. It's one you probably wouldn't need to actually solve, but simple enough that it's easy to understand and maybe surprising that there are many different solutions.

The Fibonacci story:

Leonardo of Pisa was also known as Fibonacci. He invented the Fibonacci numbers while studying the population dynamics of rabbits. More "scientifically", he was interested in many things, including a subject we now know as population dynamics: For instance, how quickly would a population of rabbits expand under appropriate conditions?

As is typical in mathematics (and analysis of algorithms is a form of mathematics), we make the problem more abstract to get an idea of the general features without getting lost in detail:

(The last assumption sounds stupid, but makes the problem simpler. After we have analyzed the simpler version, we could go back and add an assumption e.g. that rabbits die in ten years, but it wouldn't change the overall behavior of the problem very much.)

We then express the number of pairs of rabbits as a function of time (measured as a number of years since the start of the experiment):

In general F(n) = F(n-1) + F(n-2): all the previous rabbits are still there (F(n-1)) plus we get one pair of children for every pair of rabbits we had two years ago (F(n-2)).

Sounds confusing, but all you have to do is take that equation and provide a recursive algorithm. That is easy!

Induction

We often validate algorithms through proofs by induction on the input size. When algorithms are recursive, it makes them quite easy to prove with induction.