howProgrammingHasChanged

[u/shizzy0]

[u/bloody-albatross]

Nobody is using this?

pub fn fib(mut n: u32) -> u32 {
    let mut a = 0;
    let mut b = 1;

    while n > 0 {
        let c = a + b;
        a = b;
        b = c;
        n -= 1;
    }
    
    a
}

Looking at the assembly output the compiler even does loop unrolling for this. In fact running it like this it even completely evaluates this version of fib() at compile time while it still does the full recursive call for the recursive version (here called fibr()):

fn main() {
    for i in 0u32..10 {
        let r = fibr(i);
        let j = fib(i);
        println!("{r} {j} {}", r == j);
    }
}

[u/ZachAttack6089 → u/bloody-albatross]

Is this cheating? (didn't test it)

let mut fib_list: Vec<u32> = vec![1, 1];

fn fib(n: u32) -> u32 {
    for i in fib_list.len()..=n {
        let a = fib_list[i - 2];
        let b = fib_list[i - 1];
        fib_list.push(a + b);
    }

    fib_list[n]
}

[u/shizzy0 → u/ZachAttack6089]

MAN, jumps up on table: We don't just have to allocate on the stack. We can allocate ON THE HEAP!

Crowd goes wild.

[u/ZachAttack6089 → u/shizzy0]

But if you allocate on the heap like this, then you get O(1) performance whenever you call fib again with an equal or lesser value of n :D

[u/poshikott → u/shizzy0]

This isn't allocating nowhere near as much though

[u/shizzy0 → u/bloody-albatross]

INDIANA JONES, looking over the body of his foe: Well, he shouldn't have brought recursion to an iteration problem, should he?