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.