DEV Community

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)
}
Enter fullscreen mode Exit fullscreen mode

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

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

Collapse
 
connollyglen93 profile image
Glen Connolly

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