A famous recursion relation is that for the Fibonacci number sequence: F(n) = F(n - 1) + F(n - 2) with F(0) = 0 and F(1) = 1. Here is a simple, but very inefficient, implementation:

Warning: do not evaluate this block for n larger than 20 or so.

fibonacci := [:n | n > 1 ifTrue: [ (fibonacci value: n - 1) + (fibonacci value: n - 2) ] ifFalse: [ n ] ].

The reason this is a bad implementation is that there is a lot of duplicated computation. Consider evaluation of F(20).

> fibonacci value: 20 6765

Initially the block is evaluated with n = 20. During this evaluation, the block is recursively evaluated separately for n = 19 and n = 18. During the evaluation for n = 19 the block is recursively evaluated separately for n = 18 and n = 17 so there are two evaluations of the block for n = 18. The amount of duplication of effort grows as the recursion gets deepr.

Actually one can think of the recursive Fibonacci function as calculating its own difficulty. F(0) = 0 means that no calculation has no difficulty, F(1) = 1 means that the basic calculation has unit difficulty (this sets the scale of "difficulty") and F(n) = F(n - 1) + F(n - 2) means that because the calculation is recursive the difficulty is just the sum of the difficulty of calculating the two pieces. Consequently, because F(n) grows exponentially with n so does the difficulty of the recursive calculation.

It is more efficient to calculate the series directly:

> F := { 0, 1 }. > 2 to: 20 do: [ :n | F add: (F at: n - 1) + (F at: n - 2) ] > F {0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765} > F at: 20 6765

As a last bit of fun with the Fibonacci function, let's evaluate Binet's formula for F(n):

> phi := 5 sqrt + 1 / 2. "golden ratio" > phi 1.618033988749895 > binet := [ :n | (phi raisedTo: n) - (1 - phi raisedTo: n) / (5 sqrt) ]. > binet value: 20 6765 > binet value: @ 20 iota {0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181} > binet value: 38 39088168.99999999

The actual value of F(38) is 39088169.