Fibonnacci in Rust
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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); | |
} | |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
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 callget_fib_term_recursive(4)
andget_fib_term_recursive(3)
, butget_fib_term_recursive(4)
will also callget_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…