New Lint: No recursion without tail calls

[Evrey]

Based on this HIC++ guideline.

The stack explodes much faster using recursion than a huge BFS work queue would explode the heap. Therefore, if clippy detects some direct or indirect recursion that does not benefit from tail call optimisation, clippy should issue a warning along with a short description about why this is potentially bad and a short hint on how to transform recursive algorithms to iterative ones (e.g. using a work queue and BFS). And maybe a tl;dr about what tail calls are and how to make the algorithm tail recursive.

[llogiq]

I'd like to note that Rust does not have guaranteed tail call optimization (yet).

[Evrey]

I feared so. In that case the tail recursion hints would be a TODO for later.

[KamilaBorowska]

And Rust cannot have guaranteed tail call optimization. For instance, in this program, all function calls (except for println! macro) are tail recursive, and yet, they cannot be optimized, as I use stack space as sorta heap.

struct LinkedList<'a> {
    prev: Option<&'a LinkedList<'a>>,
    value: u32,
}

fn so_linked<F: Fn(LinkedList)>(linked: LinkedList, callback: F) {
    let value = linked.value;
    if value == 0 {
        callback(linked);
    } else {
        so_linked(
            LinkedList {
                prev: Some(&linked),
                value: value - 1,
            },
            callback,
        );
    }
}

fn main() {
    so_linked(
        LinkedList {
            prev: None,
            value: 99,
        },
        |ref list| {
            let mut list = list;
            loop {
                println!("{}", list.value);
                if let Some(prev) = list.prev {
                    list = prev;
                } else {
                    break;
                }
            }
        },
    )
}

[oli-obk]

@xfix guaranteed tail call optimization means that your code would fail to compile iff rust-lang/rfcs#1888 get's accepted and you'd request tail call optimization by adding the become keyword to all tail call locations