[enord]

I find the prevailing use of “recursion”, i.e. β-reduction all the way to ground terms, to be an impoverished sense of the term.

By all means, you should be familiar with the evaluation semantics of your runtime environment. If you don’t know the search depth of your input or can’t otherwise constrain stack height beforehand beware the specter of symbolic recursion, but recursion is so much more.

Functional reactive programs do not suffer from stack-overflow on recursion (implementation details notwithstanding). By Church-Turing every sombolic-recursive function can be translated to a looped iteration over some memoization of intermeduate results. The stack is just a special case of such memoization. Popular functional programming patterns provide other bottled up memoization strategies: Fold/Reduce, map/zip/join, either/amb/cond the list goes on (heh). Your iterating loop is still traversing the solution space in a recursive manner, provided you dot your ‘i’s and carry your remainders correctly.

Heck, any feedback circuit is essentially recursive and I have never seen an IIR-filter blow the stack (by itself, mind you).

[taneq]

> By Church-Turing every sombolic-recursive function can be translated to a looped iteration over some memoization of intermeduate results. The stack is just a special case of such memoization.

Ah, so functional reactive programs don’t suffer from stack overflow on recursion, they just suffer from memoisation overflow? ;)

Electronic circuits with feedback could be thought of as tail end recursion. :)

[enord]

Yes indeed! Except you can also do no memoization, such as the goto statement!

[rad_gruchalski]

And in imperative languages one can get away with no recursion. For example setTimeout(f, 0) in js or go routine in go. Of course one needs an accumulator in that case.

[enord]

Ah! That’s actually recursion again.

[Jerrrrrrry]

explain to me, exactly, how it knows what line to go to, and how to get there.

"go back to 0x00, then jump GOTO return register bits ahead"

you still have a variable, the goto return register.

it is your nested depth, the nesting limit til that register overflows.

please explain to me cuz im confused fr

[enord]

Memoization is the word here. Can be done in different ways—- of which storing the stack frame is one.