Solving the Fibonacci Sequence

#go #algorithms #challenge #discuss

I started Jon Calhoun's Algorithms With Go course this week, and I have to say it's very enjoyable. I don't know whether it's the course content or getting my hands dirty writing Go Code but it really is a great course.

Anyhoo - One of the algorithms included in the course is the calculation of the Fibonacci sequence.

The Fibonacci sequence is defined as

F(n) = F(n-1) + F(n-2)

I wrote the following solution (here's one I made earlier), but it's bothering me because I feel like it could be written in even less lines of code. Anyone care to try?
I'm not expecting Go, feel free to write it in any language you see fit, I'm just curious how compact the solution to a challenge like this can be. What better community to ask than the dev.to community?

func Fibonacci(n int) int {
    if n < 1 {
        return 0
    }
    if n < 3 {
        return 1
    }
    return Fibonacci(n-1) + Fibonacci(n-2)
}

Top comments (3)

Corey Alexander • Jul 9 '20

Rust Solution

I like doing Fib iteratively cause 🤷 So here is my iterative fib, and a version that returns a list of the fib numbers. With the iterative answer that is a pretty simply modification!

fn iter_fib(n: u64) -> u64 {
    let mut x = (0, 1);
    for _ in 0..n {
        x = (x.1, x.0 + x.1);
    }

    return x.0;
}

fn iter_fib_list(n: u64) -> Vec<u64> {
    let mut list = Vec::new();
    let mut x = (0, 1);
    for _ in 0..n {
        list.push(x.0);
        x = (x.1, x.0 + x.1);
    }

    return list;
}

fn main() {
    println!("Fib 50 = {:?}", iter_fib(50));
    println!("Fib List to 50 = {:?}", iter_fib_list(51));
}