5 ms·

recursion is always synonymous to me of unbounded memory usage. Understanding the memory consumption of a for loop updating a local variable looks easy. But a

by bsaul 5y ago

recursion is always synonymous to me of unbounded memory usage. Understanding the memory consumption of a for loop updating a local variable looks easy. But a recursive function ? forget it...

emodendroket 5y ago
Well that's why you want a function to be tail recursive, right?
- bsaul 5y ago
  yeah but how do i know for sure that the compiler is going to optimize the memory or not ? Some compilers are smarter than other to rewrite recursion in a tail recursive way, and others aren't, and it's probably not possible all the time anyway.. It seems like a very convoluted way to do a simple thing ( sometimes).
  - emodendroket 5y ago
    In Scala, as I recall, you could annotate a method as tail recursive so it wouldn't build if it weren't. A serious functional language pretty much has to have an answer for this since you're supposed to use recursion instead of iteration.
    - yawaramin 5y ago
      Scala has the '@tailrec' annotation for this, and OCaml has the '[@@tailcall]' attribute for the same reason.
  - carnitine 5y ago
    A tail recursive function can always be optimised into code which does not consume memory on recursion, and it’s a pretty basic fact to learn about a given language/implementation.
    - bsaul 5y ago
      my question was more about cases where the tail recursive version isn't possible, or even worst when the code isn't written in a tail recursive way but you expect the compiler to rewrite it to the tail recursive version. the fact that FP works over a model of computation (aka an abstraction over the underlying hardware limits) makes it a bit harder to visualize its behavior in the bounded real-world environment ( imho ). The more i progress the more i want to develop with "visible wires", and reduce the amount of abstraction to its most basic components..
  - Twisol 5y ago
    I suspect you think about recursion in terms of a call stack, yes? So when you have tail recursion, you're still pushing a frame onto the stack by default, unless the compiler recognizes that it can optimize that way. Yes? The traditional FP model of computation doesn't have a call stack. It proceeds by reduction: replace one subexpression with another, in the program text itself, and repeat until you can't do it anymore. So if I've got a fibonacci function in two clauses, `fib 0 a b = b` and `fib n a b = fib (n - 1) b (a + b)`, then a reduction may look like this: fib 3 0 1 -- initial program = fib 2 1 (0 + 1) -- substitute second clause of `fib` = fib 2 1 1 -- evaluate `+` = fib 1 1 (1 + 1) = fib 1 1 2 = fib 0 2 (1 + 2) = fib 0 2 3 = 3 -- substitute first clause of `fib` Notice how the tail-recursion naturally falls out of the substitution steps performed by the interpreter. There are no stack frames; the whole "rest of the program" (which is what a call stack is) is just the program itself. This isn't just an analogy; this is the way computation works in an FP. To an FP system, the call stack is the invisible, behind-the-scenes optimization.
  - c-cube 5y ago
    Functional languages will typically guarantee you that tail recursion is constant space. The exception is languages running on a FP adverse runtime such as the jvm, and they tend to provide a special keyword and rewrite into a loop. Also, mutual recursion is a bit more general than loops :)
    - Twisol 5y ago
      Mutual single recursion is still a loop; you just pick where you want to cut the cyclic dependencies to return to the top. In the worst case, you can put a `switch` in the loop and track what state you're in, although that's gross (you have to keep the union of all variables that might be used in each state). Multiple recursion, like in `fib n = fib (n - 1) + fib (n - 2)`, is more general than loops... in a world without higher-order functions. You can make such a function tail-recursive by doing the continuation-passing transform, which basically just makes the stack explicit. (You'd then want to "defunctionalize the continuation" [0] to clean up.) (I've actually done this in Java! Writing the multiply-recursive solution is sometimes a lot easier to do (and verify); transforming it into an iterative solution mechanically exposes a lot more hidden details, but you still have your recursive solution you can test and compare against.) [0] http://www.pathsensitive.com/2019/07/the-best-refactoring-youve-never-heard.html http://www.pathsensitive.com/2019/07/the-best-refactoring-yo...
asimpletune 5y ago
They can be made to work very much the same with the compiler. The main difference is tail recursive or not. Basically whether the answer is being accumulated along the way or requires returns from the call stack to accumulate the result. Otherwise there’s no law of computer science making the two very different. Some language compilers implement recursion naively, that’s mostly it. The call stack itself is literally just a stack provided by the OS with restrictions meant to protect the other programs in the os.
- jarcane 5y ago
  Yes. Fundamentally, the problem is cultural, not mathematical. A modern language like Racket with proper recursion optimizations will compile and optimize a recursive solution that is as fast or nearly (and even sometimes faster) than a mutable imperative one. The problem is that the idea of recursion as slow or resource hungry has become a kind of circular just-so story among imperative programmers and compiler developers who don't want to write recursion optimizations (or don't even know how). The argument goes that recursion is slow, so don't use recursion, and if you raise the idea of optimizing recursion, the compiler dev dismisses it, because why would you write recursion support, recursion is slow. Now it's fair to say in an earlier era, this was somewhat justifiable, but the logic has been passed down far longer than it's actually been true of the technology available. I remember reading "recursion bad" in C books in the 90s, and it's still so pervasive that even though TCO has been in the JS standard since ES6 years ago, most browsers still can't be bothered to support it.
dnautics 5y ago
How is this not equally applicable to "constructing an object"?
- bsaul 5y ago
  it's pretty rare to have the size of an objet in memory be proportional to the number of times one of its method is called. It's usually proportional to the amount of "data" it stores. In the case of recursion, the "time" of computation may have a direct consequence, in itself, on the occupied memory (in the case of non-tail optimized calls)

by bsaul 5y ago

recursion is always synonymous to me of unbounded memory usage. Understanding the memory consumption of a for loop updating a local variable looks easy. But a recursive function ? forget it...

emodendroket 5y ago

Well that's why you want a function to be tail recursive, right?

bsaul 5y ago
yeah but how do i know for sure that the compiler is going to optimize the memory or not ? Some compilers are smarter than other to rewrite recursion in a tail recursive way, and others aren't, and it's probably not possible all the time anyway.. It seems like a very convoluted way to do a simple thing ( sometimes).
- emodendroket 5y ago
  In Scala, as I recall, you could annotate a method as tail recursive so it wouldn't build if it weren't. A serious functional language pretty much has to have an answer for this since you're supposed to use recursion instead of iteration.
  - yawaramin 5y ago
    Scala has the '@tailrec' annotation for this, and OCaml has the '[@@tailcall]' attribute for the same reason.
- carnitine 5y ago
  A tail recursive function can always be optimised into code which does not consume memory on recursion, and it’s a pretty basic fact to learn about a given language/implementation.
  - bsaul 5y ago
    my question was more about cases where the tail recursive version isn't possible, or even worst when the code isn't written in a tail recursive way but you expect the compiler to rewrite it to the tail recursive version. the fact that FP works over a model of computation (aka an abstraction over the underlying hardware limits) makes it a bit harder to visualize its behavior in the bounded real-world environment ( imho ). The more i progress the more i want to develop with "visible wires", and reduce the amount of abstraction to its most basic components..
- Twisol 5y ago
  I suspect you think about recursion in terms of a call stack, yes? So when you have tail recursion, you're still pushing a frame onto the stack by default, unless the compiler recognizes that it can optimize that way. Yes? The traditional FP model of computation doesn't have a call stack. It proceeds by reduction: replace one subexpression with another, in the program text itself, and repeat until you can't do it anymore. So if I've got a fibonacci function in two clauses, `fib 0 a b = b` and `fib n a b = fib (n - 1) b (a + b)`, then a reduction may look like this: fib 3 0 1 -- initial program = fib 2 1 (0 + 1) -- substitute second clause of `fib` = fib 2 1 1 -- evaluate `+` = fib 1 1 (1 + 1) = fib 1 1 2 = fib 0 2 (1 + 2) = fib 0 2 3 = 3 -- substitute first clause of `fib` Notice how the tail-recursion naturally falls out of the substitution steps performed by the interpreter. There are no stack frames; the whole "rest of the program" (which is what a call stack is) is just the program itself. This isn't just an analogy; this is the way computation works in an FP. To an FP system, the call stack is the invisible, behind-the-scenes optimization.
- c-cube 5y ago
  Functional languages will typically guarantee you that tail recursion is constant space. The exception is languages running on a FP adverse runtime such as the jvm, and they tend to provide a special keyword and rewrite into a loop. Also, mutual recursion is a bit more general than loops :)
  - Twisol 5y ago
    Mutual single recursion is still a loop; you just pick where you want to cut the cyclic dependencies to return to the top. In the worst case, you can put a `switch` in the loop and track what state you're in, although that's gross (you have to keep the union of all variables that might be used in each state). Multiple recursion, like in `fib n = fib (n - 1) + fib (n - 2)`, is more general than loops... in a world without higher-order functions. You can make such a function tail-recursive by doing the continuation-passing transform, which basically just makes the stack explicit. (You'd then want to "defunctionalize the continuation" [0] to clean up.) (I've actually done this in Java! Writing the multiply-recursive solution is sometimes a lot easier to do (and verify); transforming it into an iterative solution mechanically exposes a lot more hidden details, but you still have your recursive solution you can test and compare against.) [0] http://www.pathsensitive.com/2019/07/the-best-refactoring-youve-never-heard.html http://www.pathsensitive.com/2019/07/the-best-refactoring-yo...

asimpletune 5y ago

They can be made to work very much the same with the compiler. The main difference is tail recursive or not. Basically whether the answer is being accumulated along the way or requires returns from the call stack to accumulate the result. Otherwise there’s no law of computer science making the two very different. Some language compilers implement recursion naively, that’s mostly it. The call stack itself is literally just a stack provided by the OS with restrictions meant to protect the other programs in the os.

jarcane 5y ago
Yes. Fundamentally, the problem is cultural, not mathematical. A modern language like Racket with proper recursion optimizations will compile and optimize a recursive solution that is as fast or nearly (and even sometimes faster) than a mutable imperative one. The problem is that the idea of recursion as slow or resource hungry has become a kind of circular just-so story among imperative programmers and compiler developers who don't want to write recursion optimizations (or don't even know how). The argument goes that recursion is slow, so don't use recursion, and if you raise the idea of optimizing recursion, the compiler dev dismisses it, because why would you write recursion support, recursion is slow. Now it's fair to say in an earlier era, this was somewhat justifiable, but the logic has been passed down far longer than it's actually been true of the technology available. I remember reading "recursion bad" in C books in the 90s, and it's still so pervasive that even though TCO has been in the JS standard since ES6 years ago, most browsers still can't be bothered to support it.

dnautics 5y ago

How is this not equally applicable to "constructing an object"?

bsaul 5y ago
it's pretty rare to have the size of an objet in memory be proportional to the number of times one of its method is called. It's usually proportional to the amount of "data" it stores. In the case of recursion, the "time" of computation may have a direct consequence, in itself, on the occupied memory (in the case of non-tail optimized calls)