Why the use of recursion when it's not needed?

Why is this voted as best practice, when this is slower than a linear scan?

And what if it's type become something more than a long?

You don't. As far as long is concerned number 2971215073L suffice.

It's better to use the String#replace method instead of String#replaceAll, because String#replaceAll compile regular expression always when its was call

What if you needed way more fibo numbers ^^ ? like the first 100?

You only need to return the n positive odd numbers that comes before the given n.