The specification that the Fibonacci routine has to be recursive is stupid in the first place. Forget the "unless I can do it in assembly or a language that allows stack-free re-entry and short-circuiting", recursion is not needed at all if you have some leeway in picking the best approach.
A much better solution is starting at the 3rd element, with the 1st and 2nd element being known. Then you go forward through the 4th, 5th element and so on until you reach the Nth element.
I actually got that problem as an exercise in my university days. First I did it as asked, then with a 100 element array, pre-filling the 1st and 2nd element, then working my way up.
Arguably the array variant was still a waste of memory, because you can do it in 3 variables with a bit of shifting the numbers around. But even that primitive solution was way better than the recursive approach.
This is an example of the mistake being in the head of the person who generates the questions for the test. By telling the candidates to use a specific approach, (s)he actually suppressed the best answers.