2 ms·

>And recursions are no fun, when you run out of stack space. It's been a while since I read anything about this topic but they get optimized out by the compile

by ta8903 4y ago

>And recursions are no fun, when you run out of stack space. It's been a while since I read anything about this topic but they get optimized out by the compiler in most cases, right?

MichaelMoser123 4y ago
That is possible, if the recursion call is the last statement of the recursive function (tail call optimization). Now the recursion call is not always at the end of the function, so that this optimization does not always apply. https://en.wikipedia.org/wiki/Tail_call https://en.wikipedia.org/wiki/Tail_call Now Python doesn't do tail call optimization out of the box (surprise). but there is a module that is adding some magical decorator that fixes that: https://pypi.org/project/tail-recursive/ https://pypi.org/project/tail-recursive/ (actually need to look how they implement this decorator, it must be some serious hack.)
- momentoftop 4y ago
  You can do tail call optimisation when the last thing you do before you return is a call. That tail call is not necessarily recursive, let alone a call to yourself. Whatever it is, its position means your current stack-frame can be reclaimed before you jump. If you can only optimise calls to yourself, you have a very limited form of tail call optimisation. It's an important point in the context of Scheme, where they made a big deal out of experimenting with continuation passing style. In CPS, all function calls are tail calls, and you want to optimise them all, even though most are not recursive.
jcrites 4y ago
You are probably thinking of tail-call optimization, which is when a recursive function returns the result of calling itself as its last action. These algorithms and functions are called tail-recursive. Compilers and interpreters can (more easily) optimize tail-recursive algorithms to avoid the normal cost of creating a new stack frame and making a normal function call, which means the recursive algorithm has performance more like that of an iterative implementation. https://en.wikipedia.org/wiki/Tail_call https://en.wikipedia.org/wiki/Tail_call https://llvm.org/docs/CodeGenerator.html#tail-call-optimization https://llvm.org/docs/CodeGenerator.html#tail-call-optimizat...
KingMob 4y ago
Not usually, no. Some languages support automatic tail-call optimization (when a recursive call is the returned value of a function, you can effectively replace the current stack with the recursively-called one), but in general, there are limits to how "sufficiently-advanced" real compilers are. Eliminating recursion might be difficult to detect if multiple functions form a mutually-recursive set, or if data structures have to be introduced to compensate for no stack (e.g., converting a depth-first search from recursive to iterative form requires a stack).

by ta8903 4y ago

>And recursions are no fun, when you run out of stack space. It's been a while since I read anything about this topic but they get optimized out by the compiler in most cases, right?

MichaelMoser123 4y ago

That is possible, if the recursion call is the last statement of the recursive function (tail call optimization). Now the recursion call is not always at the end of the function, so that this optimization does not always apply. https://en.wikipedia.org/wiki/Tail_call https://en.wikipedia.org/wiki/Tail_call Now Python doesn't do tail call optimization out of the box (surprise). but there is a module that is adding some magical decorator that fixes that: https://pypi.org/project/tail-recursive/ https://pypi.org/project/tail-recursive/ (actually need to look how they implement this decorator, it must be some serious hack.)

momentoftop 4y ago
You can do tail call optimisation when the last thing you do before you return is a call. That tail call is not necessarily recursive, let alone a call to yourself. Whatever it is, its position means your current stack-frame can be reclaimed before you jump. If you can only optimise calls to yourself, you have a very limited form of tail call optimisation. It's an important point in the context of Scheme, where they made a big deal out of experimenting with continuation passing style. In CPS, all function calls are tail calls, and you want to optimise them all, even though most are not recursive.

jcrites 4y ago

You are probably thinking of tail-call optimization, which is when a recursive function returns the result of calling itself as its last action. These algorithms and functions are called tail-recursive. Compilers and interpreters can (more easily) optimize tail-recursive algorithms to avoid the normal cost of creating a new stack frame and making a normal function call, which means the recursive algorithm has performance more like that of an iterative implementation. https://en.wikipedia.org/wiki/Tail_call https://en.wikipedia.org/wiki/Tail_call https://llvm.org/docs/CodeGenerator.html#tail-call-optimization https://llvm.org/docs/CodeGenerator.html#tail-call-optimizat...

KingMob 4y ago

Not usually, no. Some languages support automatic tail-call optimization (when a recursive call is the returned value of a function, you can effectively replace the current stack with the recursively-called one), but in general, there are limits to how "sufficiently-advanced" real compilers are. Eliminating recursion might be difficult to detect if multiple functions form a mutually-recursive set, or if data structures have to be introduced to compensate for no stack (e.g., converting a depth-first search from recursive to iterative form requires a stack).