r/backtickbot • • May 03 '21

https://np.reddit.com/r/computerscience/comments/n3kjbf/when_to_use_recursion/gwsoq5n/

Recursion can easily solve a problem but can be really really bad in terms of memory use for example Fibonacci numbers.

fn main() {
    println!("{}", fib(25));
}

fn fib_helper(n: u32, current: u128, next: u128) -> u128 {
    match n {
        0 => current,
        _ => fib_helper(n -1, next, current + next)
    }
}

fn fib(n: u32) -> u128 {
    fib_helper(n, 0, 1)
}

This is a trivial tail-recursive implementation that's easy for the optimizer to handle and uses constant memory in the real world. Recursion and Iteration are equivalent in optimal settings. Now there are some languages that explicitly for it tail call optimization like python, others that rely on their optimizer which can't always handle it and again others that guarantee the optimization. Those are language restrictions to be aware of. But recursion certainly isn't really really bad with memory by default.

PS: I hate the usage of Fibonacci to make recursion look bad with memory the way it's almost always taught. The good tail recursive one is really trivial, just as much as the shitty exponential version.

1 Upvotes

0 comments sorted by