This post is about simple Fibonacci Sequence in Rust using recursion and iteration. It also shows which one is faster than the other using differences of start and end times.
Fibonacci using Recursion
The fibonacci_recursive function accepts and returns an i64 value. Given a parameter n, it calls itself with n-1 and n-2 until n is less than 2 and returns the final value.
1 2 3 4 5 6 | fn fibonacci_recursive(n: i64) -> i64 { if n < 2 { return n; } return fibonacci_recursive(n - 1) + fibonacci_recursive( n - 2); } |
Fibonacci using Iteration
The fibonacci_iterative function also accepts and returns i64. Given a parameter n, it loops from 1 to n – 1. It adds up first_number and second_number in each iteration.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 | fn fibonacci_iterative(n: i64) -> i64 { let mut first_number:i64 = 0; let mut second_number:i64 = 0; let mut current_number:i64 = 1; let mut i:i64 = 1; while i < n { first_number = second_number; second_number = current_number; current_number = first_number + second_number; i = i + 1; } return current_number; } |
50th Fibonacci Number
The following codes use Instant::now() to get the current time before each of our function runs. The codes also use thee elapsed() function on an Instant object to get a Duration object. Then they use the as_millis() function on the Duration object to get the number of milliseconds from the time Instant::now() was used.
1 2 3 4 5 6 7 8 9 10 11 12 13 | use std::time::{Duration, SystemTime, Instant}; fn main() { let start_sys_time_recursive = Instant::now(); println!("{}", fibonacci_recursive(50)); println!("Recursive: {:?} ms", start_sys_time_recursive.elapsed().as_millis()); let start_sys_time_iterative = Instant::now(); println!("{}", fibonacci_iterative(50)); println!("Recursive: {:?} ms", start_sys_time_iterative.elapsed().as_millis()); } |
The codes output the following.
1 2 3 4 | 12586269025 Recursive: 179751 ms 12586269025 Recursive: 0 ms |
If we start from 10th to 60th Fibonacci number, we would get the following graph of performance between recursion and iteration in Rust. Recursion is slower and takes way more time to complete than iteration. If we push for the 60th Fibonacci number and beyond, we would need several hours or even days.
