In Go, you can define a function that returns a function. Let's call the first function A and the returned one B. The function B is defined anonymously as follow return func() returnType {} and can reference the variables of function A. In case the anonymous function do reference variables from function A, we say that B closes up on all nonlocal variables that it references to form a closure. Let's take the example of a function that generates odd numbers (example taken from the book Introducing Go Build Reliable, Scalable Programs):
func main() {
nextOdd := MakeOddGenerator()
fmt.Println(nextOdd()) // Prints 1
fmt.Println(nextOdd()) // Prints 3
}
MakeOddGenerator() func() uint {
i := uint(1)
return func() (res uint) {
res = i
i = 2 * i + 1
return
}
}
In the above example, the variable i keeps its value between the different calls of the function nextOdd. But how does it help us in computing the elements of the Fibonacci sequence ?
Well, the most used approach to compute the elements of the Fibonacci sequence is to use recursion, as a matter of fact, recursion seems to comes out naturally from the definition of the Fibonacci' sequence. So let's look at what is the Fibonacci' sequence ? It is a sequence (put it simply, a list of elements) of positive integers denoted as F or Fib defined as follow:
- Fib(0) = 0
- Fib(1) = 1
- for n greater than 1, Fib(n) = Fib(n - 1) + Fib(n - 2)
And here are the first 15 elements of the Fibonacci sequence: 0, 1 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610.
The last line Fib(n) = Fib(n - 1) + Fib(n - 2) is what gives us an intuition about using recursion for the computation. So, let's implement a recursive algorithm to compute the nth element of the Fibonacci sequence:
func FibonacciRec(x uint) uint {
if x == 0 {
return 0
} else if x == 1 {
return 1
} else {
return FibonacciRec(x-1) + FibonacciRec(x-2)
}
}
If you try this function, it may work fine with small values of x, but when I tried it with x = 50, on my machine (A Core i7 11th Gen with 16Gb of RAM running Ubuntu inside WSL2) I got these results for computing Fib(50):
I don't know for you but 1 minute is a long time for 'just' Fib(50). And it makes sense when you think about it. Let's analyse the call stack of Fib(n). If n is different from 0 or 1, you need at least two other function calls to get the answer, and for each one, if it is not 0 or 1, you also need at least two other function calls and so on and so on.
(not really a 'stack' but I thought this representation might be easier to grasp)
Now, from this 'stack', you may also notice that some values are computed twice (or more than that if you draw out the stack at a deeper depth), in order words, with the current algorithm, we cannot reuse already computed values like Fib(n-2) and Fib(n-3) in our case.
Let's try to solve this issue using closures in Go. First we want a function that returns a function:
func FibonacciDyna() func(y int) int {
return func(y int) int {
}
}
Next, we need to 'remember' the previously computed elements of the sequence, for that we add an array (or slice in Go terminology) variable to the englobing function:
func FibonacciDyna() func(y int) int {
fib := []int{0,1}
return func(y int) int {
}
}
Notice that we add the first two elements of the Fibonacci sequence. Then, we need to consider multiple cases, but before that, we also have to pay attention to how the nth element of the sequence corresponds to the nth element of our array:
func FibonacciDyna() func(y int) int {
fib := []int{0,1}
return func(y int) int {
// negative numbers are not supported
if y < 0 {
panic("negative number not supported")
}
// We already computed the value.
if y < int(len(fib)) {
return fib[y]
}
// We have the two previous value Fib(n-1) and
// Fib(n-2) needed for computation.
if y-2 >= 0 && y < len(fib) {
// Store the newly computed value
fib = append(fib, fib[y-1]+fib[y-2])
return fib[y]
}
// We don't have one or both of the two previous
// value needed for computation.
// We then compute and store all the missing values.
for i:= len(fib); i<= y; i++ {
fib = append(fib, fib[y-1]+fib[y-2])
}
return fib[y]
}
}
You can even add some tests:
func TestFibonacciOf0ShouldReturn0(t *testing.T) {
x := 0
want := 0
getFibDyn := FibonacciDynamic()
have := getFibDyn(x)
if want != have {
t.Fatalf(`FibonacciDynamic(%d) = %d, want equal for %d`, x, have, want)
}
}
func TestFibonacciOf1ShouldReturn1(t *testing.T) {
x := 1
want := 1
getFibDyn := FibonacciDynamic()
have := getFibDyn(x)
if want != have {
t.Fatalf(`FibonacciDynamic(%d) = %d, want equal for %d`, x, have, want)
}
}
func TestFibonacciOf10ShouldReturn55(t *testing.T) {
x := 10
want := 55
getFibDyn := FibonacciDynamic()
have := getFibDyn(x)
if want != have {
t.Fatalf(`FibonacciDynamic(%d) = %d, want equal for %d`, x, have, want)
}
}
And now let's run it:
Much better !
That's it, let me know what you think in the comments below !
You may find the source code here
Top comments (2)
Nice article!
Instead of keeping a slice of all numbers you can make it even more efficient by just keeping two ints and iterate from 1 to
yYes, I thought about it, but I really wanted to try the 'caching' of the values. With the slice, I can get values I already computed, without computation, so I found it more interesting, but I will definitively try your approach !