Recursive_rust_cache-article.md

Fibonacci recursive with cache in Rust

This sample program aims to show how to pass an array by reference to other function in Rust, by using an array as a cache of the calculus of fibonacci sequence.

Rust can not hold a number greater than fib(185) on a u128 (unsigned integer 128 bits) type, so the program asks first to the user the n number and performs this simple check.

The main function creates an array with all values initializated to 0, and then we refill the two first values of fibonacci sequence:

fib(0) = 1 fib(1) = 1

let mut fibs: [u128; 200] = [0;200];
fibs[0] = 1;
fibs[1] = 1;

This array is created using mut keyword, and then is passed to another function by its reference: &mut.

fibonacci_cache(uinput_n, &mut fibs)

The function will refill all fibonacci values and will compute them only once. This method is faster than running the traditional version of recursive fibonacci, and uses less memory from the stack, allowing larger numbers to be computed.