MATLAB: Computing Recursive Function Efficiently

recursive function

I've got a function that is recursive:
i.e. f(x) = kf(x – 1)
(Where k is complicated)
I need to find the value of f(0), f(1), . . ., f(n).
Is the most efficient way to do this to calculate f(0) and store it, and then use this to calculate f(1), and so on?

Best Answer

Use a loop. What is the problem? Why do you need to use recursion at all?
- Don't forget that MATLAB always uses 1-based indexing.
- Don't forget to preallocate a vector for the results, IF you need to retain them all. If all you need is the final element, there is no need for preallocation.
Compute f(0). Then loop from 1 to n. Computing f(1), f(2), etc. Stop when you get to n. This is the essence of a loop.
Surely you get the gist.
Use of a recursive scheme here is silly, since it forces additional function call overhead for every recursive step. Memory must be allocated, variables passed. That all takes cpu cycles. (You said you wanted efficiency.) And there are limits on the recursive depth you can descend to anyway.
You are looking for a fancy, sophisticated looking solution, when a simple one is available, at no real cost. The overhead of a loop is almost non-existent, certainly compared to anything else you might try.
My guess is you are asking to do this because of one of...
1. You are pre-optimizing, worrying about the cost of something before you see it is a problem. NEVER do this. Write reasonable code, and only optimize it when you see a bottleneck arise.
2. You have a known time problem. But the fact is, you said yourself that it is the computation of the multiplier that is expensive. (Or something equivalent to that multiplier.) So worrying about loop overhead is silly. Spend your time optimizing whatever it is that is actually taking up time.
Related Question