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...
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.
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.
It seems like a very convoluted way to do a simple thing ( sometimes).
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..
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`
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.
Also, mutual recursion is a bit more general than loops :)
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-yo...
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)