Skip to content

Instantly share code, notes, and snippets.

@brandonio21
Created May 23, 2015 03:21
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
Star You must be signed in to star a gist
Save brandonio21/0717dd1e5d46cca12422 to your computer and use it in GitHub Desktop.
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
Copy link

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