Gödel, Escher, Bach An Eternal Golden Braid by Douglas R. Hofstadter

FlBO(n):

FIGURE 30. Diagram G, further expanded and with numbered nodes.

defined recursively by the pair of formulas

FIBO(n) = FIBO(n - 1) + FIBO(n - 2) for n > 2

FIBO(l) = FIBO(2) = 1

Notice how new Fibonacci numbers are defined in terms of previous

Fibonacci numbers. We could represent this pair of formulas in an RTN

(see Fig. 31).

let x = FlBO(n-l) let y = FlBO(n-2)

value is 1

FIGURE 31. An RTN for Fibonacci numbers.

Thus you can calculate FIBO(l5) by a sequence of recursive calls on the

procedure defined by the RTN above. This recursive definition bottoms

out when you hit FIBO(l) or FIBO(2) (which are given explicitly) after you

have worked your way backwards through descending values of n. It is

slightly awkward to work your way backwards, when you could just as well

work your way forwards, starting with FIBO(I) and FIBO(2) and always

adding the most recent two values, until you reach FIBO(l5). That way you

don't need to keep track of a stack.

Now Diagram G has some even more surprising properties than this.

Its entire structure can be coded up in a single recursive definition, as

follows:

136 Recursive Structures and Processes