It depends on your perspective, which can depend on how the topic was presented. One approach (perhaps the mathematical one) is F_0 = F_1 = 1, F_n = F_{n-1} +

It depends on your perspective, which can depend on how the topic was presented. One approach (perhaps the mathematical one) is F_0 = F_1 = 1, F_n = F_{n-1} + F_{n-2}, so you generate the series 1, 1, 2, 3, 5, 8, ... That is, at the time you want F_n, you have already generated the series up to that point, and so you just add 2 numbers you already have. On the other hand, if I ask you to compute F_1000, it might appear very recursive. You know you could make F_1000 from F_999 and F_998. And you get F_999 from... But it wouldn't be impossible to answer this question with the same approach as the first. It's not a priori obvious that "I'll calculate F_0 ... F_999" is an efficient way to calculate F_1000, but of course that turns out to be much more efficient than the naive recursive solution. But I think Fibonacci is not the best introduction because of this. I think something like GCD calculation would be a better problem to define recursively, because there really isn't an obvious "forwards" approach to oppose the "backwards" Euclidean algorithm.