Picking on Fibonacci of all things? The goal of fibonacci and factorial examples are to teach recursion. Both fibonacci and factorial are good starting points for a beginner. It can be followed by discussions of dynamic programming where the student can be introduced to recurrence relations and solving them top-down and bottom-up.
EDIT: Adding some background on dynamic programming
For dynamic programming, the problem should be breakable in terms of overlapping smaller problems, and the base case should be recognized. If the problems don't overlap, they fall within broader divide and conquer category(mergesort, quicksort etc are famous examples).
fib(n) is defined as fib(n-1) + fib(n-2) (overlapping smaller subproblems) and fib(0) = 1 and fib(1) = 1 (base cases)
fib(n) = fib(n-1) + fib(n-2)
fib(0) = 0
fib(1) = 1
A relation defined as above(recursively) is known as recurrence relation. Discrete math courses deal with finding closed form expression - a non-recursive function of n. But in programming, we are fine with solving the recurrence relation without finding a closed form expression.
Recurrence relations form the basis of dynamic programming and they can be solved either top down or bottom up.
The top down approach is the traditional recursive solution.
def fib(n):
if n == 0 or n == 1: return n
return fib(n-1) + fib(n-2)
And then the student is to realize fib(n-1) is recalculating fib(n-2) and memoization is in order.
def fib(n):
cache = {0: 0, 1: 1}
def _fib(n):
if cache.has_key(n): return cache[n]
cache[n] = _fib(n-1) + _fib(n-2)
return cache[n]
return _fib(n)
Then the student should realize modifying every function isn't apt, and should implement a general memoize decorator.
EDIT: Adding table based bottom up fibonacci.
Now once the student understands top down dynamic programming, as in he can find the recurrence relations and base cases, it's time for bottom up. As the name suggests, bottom up starts from the bottom and calculates n compared to top down which starts from n and boils down to base cases.
def fib(n):
vals = {0: 0, 1: 1}
for i in range(2, n+1):
vals[i] = vals[i-1] + vals[i-2]
return vals[n]
Student should recognize how top down and bottom up are calculating the same recurrence relation, but in a different order. The table vals here is the same as cache above in top down.
Top down is recursive and might trigger the recursion limit. Bottom up doesn't have the recursion problem. Sometimes in case of bottom up, table can be eliminated depending on the overlap. But the important thing is, once the recurrence and base cases are known, it can be implemented quite easily.
In fibonacci's case, nth number depends only on n-1 and n-2 and maintaining the whole table is wasteful. The bottom up approach will be better.
def fib(n):
f0, f1 = 0, 1
for i in range(n-1):
f2 = f0 + f1
f0, f1 = f1, f2
return f2
Fibonacci just happens to be one of the problems used to demonstrate recursion and dynamic programming. It's small enough for a beginner to comprehend, and big enough to explain recursion and dynamic programming.
The article picks one recurrence which has a closed form expression. The dynamic programming problems which I have encountered aren't that easily reduced to closed form expressions.
Also, I don't know about Graham or Raymonds, but Yegge advocates maths for programmers.
http://steve-yegge.blogspot.in/2006/03/math-for-programmers....