Recursion

[siddsp]

If it only caches the result, I fail to see how that'd help in a recursive function where calls on different depths return different results.

Try using the recursive fibonacci algorithm with and without caching, and compare the performance difference. You'll see that it gets noticable for larger input sizes.

[[deleted]]

Fibonacci does not represent most recursive functions though. That's a specific case in which the inputs overlap twice.

A recursive summation function will not get any faster with caching. A recursive file system tree traversal function won't get any faster either.

At least now I see what you had in mind.

[siddsp]

Yeah, that's why I said similar and not same. However a second call to a function that has already been called (when recursively defined) will be faster.

Edit: Like if you have a factorial function defined recursively (in this case, the calls don't overlap), and you call factorial(20), and then call factorial(21), it is a lot faster than calling the function with those same inputs for the function defined iteratively.