# Why is recursive programming problematic for branch predictors

Consider for example the following recursive program:

function fibonacci(int n) {
if (n < 2) {
return 1;
} else {
return fibonacci(n - 2) + fibonacci(n - 1);
}
}


The question is now, why recursive programs are problematic for branch predictors? I think that this is due to the fact that the branch-instruction inside these programs follows a very hard to predict pattern. When considering for example fibonacci(4), it holds that

fibonacci(4) = fibonacci(2) + fibonacci(3)

fibonacci(4) = fibonacci(0) + fibonacci(1) + fibonacci(1) + fibonacci(2)

fibonacci(4) = fibonacci(0) + fibonacci(1) + fibonacci(1) + fibonacci(0) + fibonacci(1).

Thus the following function calls will be performed in this order: fibonacci(2), fibonacci(3), fibonacci(0), fibonacci(1), fibonacci(1), fibonacci(2), fibonacci(1), fibonacci(0). This results in following sequence of Taken / Not Taken for the if-statement: NT NT T T T NT T T, which is quite irregular.

My question is now, if my answer and reasoning is correct?

• Your statement sounds interesting and makes some sense. I'm curious though where you found the claim that recursion isn't very predictor-friendly, or why you thought originally that it's true. (I haven't come across it before.) – Omar Dec 9 '17 at 13:31
• @Omar It's a question that was asked by the teacher on a test in our advanced computer architecture course, and I was curious if my answer makes sense – Pieter Verschaffelt Dec 9 '17 at 14:32
• In terms of conditional branch prediction, recursion is not problematic. However, recursion can needlessly overflow a processor's return address stack (an address predictor in the front end), so no return address prediction will be available for older returns. Recursion can be converted to a looping structure by a sufficiently clever compiler, allowing the programmer to use recursion without performance loss. – Paul A. Clayton Dec 10 '17 at 13:00
• @PaulA.Clayton I did not think about the Return Address Stack. This is indeed a very good remark and will definitely impact performance. Thank you – Pieter Verschaffelt Dec 10 '17 at 14:52