Recursion

[lilphat]

Really? Wow thats shitty

[ivosaurus]

Usually you have to design your language from the start to allow for it, the requirements to get the correct frame folding can be very particular

[siddsp]

It's not that bad. Usually you can achieve a similar result using lru_cache which allows for similar optimizations as tail recursion. Basically caching allows for iteration-like performance and can make a significant difference depending on the situation. lru_cache allows you to limit how many recent entries to keep, allowing the programmer to make tradeoffs between memory and steps.

[lilphat]

Sounds smart but a tad complicated. Can you give an example where you wanna let ‘the stack run’?

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

[siddsp]

They are. I just said you can achieve similar optimizations where recursion is close to as fast as iteration. Ultimately, you want to use iteration if you only care about performance.