Chapter 1: Recursion Solutions

Factorial

Fibonacci: A recursive algorithm

Definition: f0=0, f1=1, fi = fi-1+fi-2

The original formula seems to give us a natural example of recursion:

Algorithm 1:

    int fib(int n)
    {
    if (n == 0) return 0  
    if (n <= 2) return 1  // fine since a method only returns once so it will not do both if's
      else return fib(n-1) + fib(n-2)
    }

Binomial Coefficient: A recursive algorithm

What are they?

stop states (n = m and m = 0). Why?

Also, binomial base:

How am I sure I will get to a stop state?

Algorithm binomial(n, m) { if (n == m) then return 1; else { if (m == 0) return 1; else { x = binomial(n-1, m); y = binomial(n-1, m-1); return = x + y; } }

For fun, you could prove by induction. :-)

Ackerman's function: A recursive algorithm

A(m,n) =

TRY YOURSELF!!!!!

Powerset: A recursive algorithm

If S = (a, b, c) then the powerset(S) is the set of all subsets

powerset(S) = {(), (a), (b), (c), (a,b), (a,c), (b,c), (a,b,c)}

The first "trick" is to try to define recursively.

What would be a stop state?

S = () has what powerset(S)?

How get to it?

Reduce set by one element

Consider taking an element out - in the above example, take out {c}

S = (a,b) then powerset(S) = {(), (a), (b), (a,b), }

What is missing?

powerset(S) = { (c), (a,c), (b,c), (a,b,c)}

hmmm

Notice any similarities? Look again...

powerset(S) = {(), (a), (b), (c), (a,b), (a,c), (b,c), (a,b,c)}

take any element out

powerset(S) = {(), (a), (b), (c), (a,b), (a,c), (b,c), (a,b,c)} IS

powerset(S - {c}) = {(), (a), (b), (a,b)} unioned with

{c} U powerset(S - {c}) = { (c), (a,c), (b,c), (a,b,c)}

powerset(S) = powerset(S - {ei}) U ({ei} U powerset(S - {ei}))

where ei is an element of S (a singleton)

Pseudo-algorithm

  1. Is the set passed empty? Done
  2. If not, take an element out
    • recursively call method on the remainder of the set
    • return the set composed of the Union of
      (1) the powerset of the set without the element (from the recursive call)
      (2) this same set (i.e., (1)) but with each element therein unioned with the element initially taken out

Go backwards:

powerset(S) when S = {()} is {()}

powerset(S) when S = {(a)} is {(), (a)}

powerset(S) when S = {(a,b)} is {(), (a), (b), (a,b)}

etc...