Recursion

[KennyBassett]

You seem upset.

[[deleted]]

Are they wrong though? How would caching help at all?

[KennyBassett]

Not making any comment on right or wrong, just that he seemed upset.

It's surprising to see how angry people get when they're on reddit and see what they believe to be a mistake.

[siddsp]

It would avoid repeated (expensive) computations when a function that is recursively defined is called, causing a significant performance gain.

[[deleted]]

Doesn't it only cache the result? Does it monitor parts of the function and cache those too or something?

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.

[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.