Algorithms: 2. The Fibonacci Sequence

Mar 19, 2022

Introduction #

The Fibonacci sequence is probably one of the best know number sequences, with each number in the sequence being the sum of the two numbers that precede it, with 0 and 1 normally being the first two numbers of the sequence. The mathematical equation describing it is Xn+2= Xn+1 + Xn.

Solution Using a For Loop #

We can use the basic structure of the fizzbizz program as a template for writing this program. There are various ways to program the fibonacci sequence. The simplest way is to use a for loop. The more elegant solution is to use recursion. For this program we will assume that the only user input is to be able to specify the number of terms the user wants to calculate for the sequence.

Using a for loop the program would look like this.

// fibonacci_with_for.go
package main

import (
    "flag"
    "fmt"
)

func fibonacci(number int) (result []int64) {

    for i := 0; i < number; i++ {
        if i == 0 {
            result = append(result, 0)
        else if i == 1 {
            result = append(result, 1)
        } else {
            // If the next value overflows the size of the int64, the value with be negative
            tmp := result[i-1] + result[i-2]

            if tmp < 0 {
                fmt.Printf("\nWARNING: For count == %d, the resulting value is greater than that allowed for an int64\n\n", i)
                return result
            }

            result = append(result, tmp)
        }
    }

    return result
}

func main() {

    var number int
    var result []int64

    // Define the flags and their default values
    flag.IntVar(&number, "number", 10, "The number of terms to calculate")
    flag.Parse()

    // Calculate the fibonacci sequence recursively
    result = fibonacci(number)

    // Print the fibonacci sequence
    for i := 0; i < len(result); i++ {
        fmt.Printf("%d ", result[i])
    }

    fmt.Printf("\n")
}

Most of this program should be fairly obvious. The bit that may not be is why we calculate the result and then check it for less than zero. The maximum number an int64 can take is 9,223,372,036,854,775,807. If the number calculated is greater than that, the number will overflow, and the result will be negative. We can check for this and just return everything up to the point before it becomes negative.

To prove that it will go negative we can write a little program:

// overflow.go
package main

import "fmt"

func main() {

    var i int64
    var number int64 = 9223372036854775800

    for i = 1; i <= 10; i++ {
        fmt.Printf("9223372036854775800 + %+v = %+v\n", i, number+i)
    }
}

If we run this we get the following output:

9223372036854775800 +  1 =  9223372036854775801
9223372036854775800 +  2 =  9223372036854775802
9223372036854775800 +  3 =  9223372036854775803
9223372036854775800 +  4 =  9223372036854775804
9223372036854775800 +  5 =  9223372036854775805
9223372036854775800 +  6 =  9223372036854775806
9223372036854775800 +  7 =  9223372036854775807
9223372036854775800 +  8 = -9223372036854775808
9223372036854775800 +  9 = -9223372036854775807
9223372036854775800 + 10 = -9223372036854775806

Solution Using Recursion #

Next we will try using recursion to solve the fibonacci sequence. Recursion can be a powerful technique for solving certain types of problems, but getting it right can be difficult if you are not use to thinking that way. Certain languages, for example functional languages, force you to use recursion as they (in general) don’t have loop structures. So let’s have a look at the program for the fibonacci sequence written using recursion.

// fibonacci.go
package main

import (
    "flag"
    "fmt"
)

func fibonacci(initial int64, next int64, count int, number int) (result []int64) {

    if count == 1 {
        result = append(result, 0)
    } else {
        result = append(result, initial)
    }

    // Stop when we hit the number of iterations we were asked to do
    if count == number {
        return result
    }

    count = count + 1
    tmp := next
    next = initial + next
    initial = tmp

    // The next value goes negative if the value overflows that of an int64
    if next < 0 {
        fmt.Printf("\nWARNING: For count == %d, the resulting value is greater than that allowed for an int64\n\n", count)
        return result
    }

    result = append(result, fibonacci(initial, next, count, number)...)

    return result
}

func main() {

    var number int
    var result []int64

    // Define the flags and their default values
    flag.IntVar(&number, "number", 10, "The number of terms to calculate")
    flag.Parse()

    // Calculate the fibonacci sequence recursively
    result = fibonacci(0, 1, 1, number)

    // Print the fibonacci sequence
    for i := 0; i < len(result); i++ {
        fmt.Printf("%d ", result[i])
    }

    fmt.Printf("\n")
}

There are ways I could make this program shorter, but the sake of explanation I have expanded the steps out to make it more clear. Note that in the main program we call the fibonacci function and pass in four parameters - the initial value, the next value, a count and the number of terms we want to calculate. The number is the value the user has given us as to the numbers of terms to calculcate and thus gives us our exit condition. The count is what gets incremented each time we call the fibonacci function so that we know how many terms we have calculated so far. When the count and the number are the same we know we need to exit. The initial and next values are the the first two numbers in the sequence, in this case 0 and 1.

Once we get into the fibonacci function the sequence of events essentially looks like this:

flowchart TB S1{"If count == 1"} -- Yes --> S11("result.append(0)") S1{"If count == 1"} -- No --> S12("result.append(initial)") S11 --> S2("Exit if count == number") S12 --> S2("Exit if count == number") S2 --> S3("count += 1") S3 --> S4("tmp := next
next = initial + next
initial = tmp") S4 --> S1

As you can see, recursion is just a loop with an exit point. If you get that exit point wrong, or you forget to add 1 to the count, for example, the loop won’t terminate.

There is one improvement we can make. Where we set initial to next and the next to initial + next, we can write that in a shorter form like this:

initial, next = next, initial+next

rather than the longer form of

tmp := next
next = initial + next
initial = tmp

Testing #

Now we can run go build and then test the program.

Show the usage

./fibonacci --help
Usage of ./fibonacci:
  -number int
        The number of terms to calculate (default 10)

Running it with the default values

./fibonacci
0 1 1 2 3 5 8 13 21 34

Test with an invalid number of terms

./fibonacci --number=-1.0
invalid value "-1.0" for flag -number: parse error
Usage of ./fibonacci:
  -number int
        The number of terms to calculate (default 10)

Test to see what happens if the number of terms overflows the int64 size

./fibonacci --number=100

WARNING: For count == 93, the resulting value is greater than that allowed for an int64

0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765 10946 17711 28657 46368 75025 121393 196418 317811 514229 832040 1346269 2178309 3524578 5702887 9227465 14930352 24157817 39088169 63245986 102334155 165580141 267914296 433494437 701408733 1134903170 1836311903 2971215073 4807526976 7778742049 12586269025 20365011074 32951280099 53316291173 86267571272 139583862445 225851433717 365435296162 591286729879 956722026041 1548008755920 2504730781961 4052739537881 6557470319842 10610209857723 17167680177565 27777890035288 44945570212853 72723460248141 117669030460994 190392490709135 308061521170129 498454011879264 806515533049393 1304969544928657 2111485077978050 3416454622906707 5527939700884757 8944394323791464 14472334024676221 23416728348467685 37889062373143906 61305790721611591 99194853094755497 160500643816367088 259695496911122585 420196140727489673 679891637638612258 1100087778366101931 1779979416004714189 2880067194370816120 4660046610375530309