DEV Community šŸ‘©ā€šŸ’»šŸ‘Øā€šŸ’»

DEV Community šŸ‘©ā€šŸ’»šŸ‘Øā€šŸ’» is a community of 963,274 amazing developers

We're a place where coders share, stay up-to-date and grow their careers.

Create account Log in
Cover image for Solving the Fibonacci Sequence
Glen Connolly
Glen Connolly

Posted on

Solving the Fibonacci Sequence

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

or

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)

Collapse
 
coreyja profile image
Corey Alexander

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));
}

play.rust-lang.org/?version=stable...

Collapse
 
limitedeternity profile image
Marise Hayashi • Edited on

Haskell (the classic solution):
fibs = 0 : 1 : zipWith (+) fibs (tail fibs)
Then: take 10 fibs

Collapse
 
connollyglen93 profile image
Glen Connolly Author

This was pretty much exactly what I was looking for. To be completely honest, I knew some functional language would swoop in with a one liner

Take a look at this:

Settings

Go to your customization settings to nudge your home feed to show content more relevant to your developer experience level. šŸ›