Create a gist now

Instantly share code, notes, and snippets.

What would you like to do?
Fibonnacci in Rust
use std::io;
fn main() {
loop {
println!("Enter the term that you want to generate!");
let mut term = String::new();
io::stdin().read_line(&mut term)
.ok()
.expect("Failed to read line!");
// convert string to int
let term: usize = match term.trim().parse() {
Ok(num) => num,
Err(_) => {
println!("Please enter a valid number!");
continue;
}
};
// Get the fib term
let mut fib_number = get_fib_term_dynamic(term);
println!("Dynamic Term number {} is {}",term, fib_number);
fib_number = get_fib_term_recursive(term);
println!("Recursive term number {} is {}", term, fib_number);
}
}
fn get_fib_term_recursive(term: usize) -> u32 {
match term {
0 => 0,
1 => 1,
_ => get_fib_term_recursive(term-1) + get_fib_term_recursive(term-2),
}
}
fn get_fib_term_dynamic(term: usize) -> u32 {
let mut v = vec![0u32, 1];
for i in 2..(term+1) {
let sum = v[i-1] + v[i-2];
v.push(sum);
}
return v[term];
}
#[test]
fn it_works() {
assert!(get_fib_term_recursive(5) == 5);
assert!(get_fib_term_recursive(6) == 8);
assert!(get_fib_term_dynamic(5) == 5);
assert!(get_fib_term_dynamic(6) == 8);
}

adud commented Nov 11, 2017

Hello,
there is a little issue with your recursive algorithm : its complexity is exponantial, because you computes many times the same term (for instance, get_fib_term_recursive(5) will call get_fib_term_recursive(4) and get_fib_term_recursive(3), but get_fib_term_recursive(4) will also call get_fiib_term_recursive(3) etc... (the french wikipedia's web page explains the differents algorithms here).
Anyway, recursivity has always been as elegant as treacherous…

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment