Recursion Examples

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?

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

Book Exercises: page 54

#24 Fibonacci

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

TRY YOURSELF!!!!!

#26 Ackerman's function: A recursive algorithm

A(m,n) =

TRY YOURSELF!!!!!

#29 Subset Generation (Powerset)

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
  3. of this set adds the element 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...

code