Let’s look at another Y-Combinator example in Go to improve our grasp of the topic. Remember the Fibonacci
function in Chapter 1, Pure Functional Programming in Go? It looked like this:
func fib(x int) int { if x == 0 { return 0 } else if x <= 2 { return 1 } else { return fib(x-2) + fib(x-1) } }
If it passes a 0
, 1
, or 2
, it simply returns a value (0
or 1
). Otherwise, it will call itself (recursion) with two functions that look like this--fib(x-2) + fib(x-1)
. Since values are continually being decremented by two or one, processing will eventually complete, at which time the accumulated values will be summed up.
The following diagram illustrates this recursive processing. The orange and red boxes highlight functions that only need to be executed once. Referential integrity allows us to store the value of those functions. Subsequent execution only needs to look up the stored value, rather than re-execute the function:
We define three function types in main.go
, as...