Rust, Software Development

Rust – Fibonacci using Recursion and Iteration

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.

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.

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.

The codes output the following.

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.

Fibonacci using Recursion and Iteration


You Might Also Like

Leave a Reply

Your email address will not be published. Required fields are marked *