n-th Fibonacci number with memoization I am learning Rust and decided to create a simple program to calculate n-th Fibonacci number. It uses a vector for memoization. The program works, but what would you suggest to improve here? Maybe store memo inside fib function as a static variable?
I tried to use u32 everywhere, but 48-th fib number doesn't fit into u32, so I decided to use u64.
use std::io;
use std::io::Write;
use std::str::FromStr;

fn fib(n: u32, memo: &amp;mut Vec&lt;u64&gt;) -&gt; u64 {
    if n &lt; 2 {
        return n as u64;
    }
    else if memo[(n-1) as usize] != 0 {
        return memo[(n-1) as usize];
    }

    memo[(n-1) as usize] = fib(n - 1, memo) + fib(n - 2, memo);
    memo[(n-1) as usize]
}

fn main() {
    loop {
        print!(&quot;n = &quot;);
        io::stdout().flush().unwrap();

        let mut str: String = String::new();
        io::stdin().read_line(&amp;mut str)
            .expect(&quot;Error getting number&quot;);

        str.pop();
        match u32::from_str(&amp;str) {
            Ok(n) =&gt; {
                let mut memo: Vec&lt;u64&gt; = vec![0; n as usize];
                println!(&quot;fib({})={}&quot;, n, fib(n, &amp;mut memo));
                break;
            }
            Err(_e) =&gt; {
                println!(&quot;Error parsing number.&quot;);
                println!(&quot;Try again&quot;);
            }
        };
    }
}
I like this. Your code is clean and pretty readable. I recommend using rustfmt, if only because it will stop annoying people on the internet from recommending you use rustfmt. But the minor code formatting differences are not something to be overly concerned about, if you have a style and stick with it.
I have two major suggestions:

Don't populate the cache with a sentinel value (zero) and then test whether each value is zero or not. Instead, make the vector start small and grow as you populate it. To avoid reallocation, you can initialize it with a large capacity and small length. You can further simplify the logic by (a) using push to add a value to the cache when you know the length is n; and (b) initializing the cache to [0, 1], which will play into the next point:

Split fib into two functions: one that takes a cache as argument, and one that creates the cache inside itself (and calls the first one to do the heavy lifting). If you expose both of these in an API, then the user can decide whether reusing the cache is appropriate or not.


Here's the main code with both suggestions implemented:
fn fib_cached(n: u32, memo: &amp;mut Vec&lt;u64&gt;) -&gt; u64 {
    if (n as usize) &lt; memo.len() {
        memo[n as usize]
    } else {
        let ret = fib_cached(n - 2, memo) + fib_cached(n - 1, memo);
        // At this point we know that memo.len() is at least n, because
        // fib_cached(n - 1, memo) will have populated memo[n-1]. Furthermore, if
        // memo.len() had been greater than n, we would have taken the other
        // branch of the if. There are no other functions capable of modifying
        // memo because we hold a &amp;mut reference to it, so memo.len() is exactly n
        // and push(ret) will make memo[n] = ret.
        memo.push(ret);
        ret
    }
}

fn fib(n: u32) -&gt; u64 {
    let mut cache = Vec::with_capacity(n as usize);
    cache.extend(&amp;[0, 1]);
    fib_cached(n, &amp;mut cache)
}

Here are some more observations, in no particular order:

Even this modified version is somewhat fragile, since it's easy to call fib_cached with a too-small cache, which may panic. If you were writing a library for others to use, I would suggest making a wrapper type around Vec&lt;u64&gt; so you can insist on correctly-initialized caches. This would be a start:
struct FibCache {
    data: Vec&lt;u64&gt;,
}

impl FibCache {
    fn with_capacity(n: usize) -&gt; Self {
        let mut data = Vec::with_capacity(n);
        data.extend(&amp;[0, 1]);
        FibCache {data}
    }
}

fn fib_cached(n: u32, memo: &amp;mut FibCache) -&gt; u64 {
    if (n as usize) &lt; memo.data.len() {
        memo.data[n as usize]
    } else {
        let ret = fib_cached(n - 2, memo) + fib_cached(n - 1, memo);
        memo.data.push(ret);
        ret
    }
}

fn fib(n: u32) -&gt; u64 {
    let mut cache = FibCache::with_capacity(n as usize);
    fib_cached(n, &amp;mut cache)
}

This means nobody can call fib_cached without creating a FibCache object with a constructor you define. It also lets you make backwards-compatible changes to the type of cache -- you could use a HashMap, as 6005 suggests, or another data structure, without changing the outward-facing API of the library.

n as usize is another source of fragility. Casting between integer types can have surprising results, so you're usually well-advised to use usize::try_from(n).unwrap() instead, which will panic if the conversion can't be done. In this code, I don't regard this as a major issue because u32 is losslessly convertible to usize on virtually all Rust targets and because any n that would overflow a usize, on any target, is already too large for this algorithm. Just be aware you should normally use the conversion traits instead of casting.

Changing fib to use internal static state is pretty simple, using lazy_static or once_cell. I'll use lazy_static here, and assume the FibCache API above:
fn fib(n: u32) -&gt; u64 {
    use lazy_static::lazy_static; // 1.4.0
    use std::sync::Mutex;
    lazy_static! {
        static ref CACHE: Mutex&lt;FibCache&gt; = Mutex::new(FibCache::with_capacity(10));
    }
    fib_cached(n, &amp;mut *CACHE.lock().expect(&quot;Could not lock static cache&quot;))
}

Whether this is a good idea or not is rather up for debate. Ultimately it's replacing contention for one resource (the heap) with contention for another resource (the lock). Neither is necessarily the best choice, which is why it's important to expose fib_cached as well so your users aren't stuck with your choice of implementation for fib. Making access to FibCache lock-free could make static memory much more appealing by removing the contention aspect.

Don't use str as the name of a variable, since it's also the name of a built-in type. It will mess with syntax highlighting (as it does on this very site).

Obviously, this is a slow and wasteful algorithm for calculating Fibonacci numbers. So I assume what you're looking for is feedback on the general shape and style of the solution, not the choice of algorithm, and I've written this review based on that assumption. Peter's review deals with algorithmic improvements.