Remix.run Logo
remram 8 months ago

An crucial point for me was realizing that "recursive CTEs" are not really recursive but better understood as iterative, in other words a loop. The results of each iteration are fed into the next iteration, until no new result is produced.

eru 8 months ago | parent | next [-]

Yes, iteration is a special case of recursion.

cryptonector 8 months ago | parent [-]

All recursion is iteration. Sometimes you have a stack to help you, and other times you get tail recursion optimization, but it's always a loop.

eru 8 months ago | parent | next [-]

What makes you think so?

Please have a look at the formal definition of regular expressions at https://en.wikipedia.org/wiki/Regular_expression#Formal_defi... on Wikipedia, and let me know where the stack and the iterations are. I can't find them.

https://en.wikipedia.org/wiki/Recursive_definition#Well_form... is also a good example.

Regular expressions are a particularly interesting example because you brought up 'loops', so I'm assuming you are interested in how you can implement some of these recursive definitions on a computer.

So for regular expressions a common technique is to compile them to a finite state machine. You can model that in your computer as one block of eg assembly instruction per machine state. To move to a different state, you just 'jmp' to the corresponding code's address.

That's pretty fun to work out, but I still don't see anything I would describe as a 'loop' here; but the recursive analysis still makes perfect sense.

Yes, some programming languages have special purpose looping constructs. But they are of limited usefulness, and not particularly fundamental: they usually get compiled away.

vincnetas 8 months ago | parent | prev [-]

all iterations are recursion but not the other way around.

cryptonector 8 months ago | parent [-]

When you add an explicit stack to help you keep state then you can have recursion be the same as iteration. Normally the stack you get in recursion is implicit rather than explicit.

eru 8 months ago | parent [-]

A stack is one way to implement a specific kind of recursion on a computer.

But see https://news.ycombinator.com/item?id=42234121 for other examples of recursion.

fifilura 8 months ago | parent | prev [-]

Isn't recursion exactly that? A loop that feeds into the next iteration.

Shraal 8 months ago | parent [-]

It's important to differentiate between tail-recursive functions and non-tail-recursive functions. Compilers will often convert tail-recursive functions into their iterative counterparts. See: https://en.wikipedia.org/wiki/Tail_call

In contrast, non-tail-recursive functions will make the call stack grow with each call.

fifilura 8 months ago | parent [-]

They both fit the description in GP.

"The results of each iteration are fed into the next iteration, until no new result is produced."