Why is recursive programming problematic for branch predictors
It would seem that recursion isn't the problem at all, but a pattern of branches that is hard to predict. For example, if you calculate n! using recursions (if n = 0 -> return 1 else return n * factorial (n-1)) that should play very nicely with branch prediction. For example 25! will start with 25 taken branches, followed by one branch not taken. 

If you calculated fib (n) by simulating the recursion using a stack, you would have mostly a loop, with the exact same branches inside the loop, and as far as branch prediction is concerned, it would be just as good / bad with no recursion anywhere in sight.

PS. This was about predicting whether a branch is taken or not taken. Newer processors use other branch-related predictions: Predicting the target of a branch (for example for virtual functions, where a branch will lead to one of possibly many implementations of a virtual functions), and prediction of the target of a "return" instruction, where the processor predicts that a "return" instruction most likely branches to the instruction after the previous "call subroutine" instruction.