4 ms·

A recursion is a cycle in the graph of function calls. Decomposing a problem into functions is something else.

by madez 9y ago

AstralStorm 9y ago
Indeed. That is a concise definition of recursion. But why have a cycle in a call stack (implicitly linearizing a graph) when you can replace it with a cycle in your data structure without spooky action at a distance controlled by a compiler? In an explicit representation of the "work graph" you can easily prove a finite number of walks or a cycle (and then break it in some way). Doing that directly for a nontrivial function without using graph theorems is much harder. Yes it is "easier" syntactically but then also easy to shoot yourself in the foot. Since a function call is a primitive you only get primitive tools to handle problems with it. Exceptions for example tend to unwind the stack which can take a long time. In functional languages you can end up with Bottom state from nowhere or a plain old crash.
jerf 9y ago
That's a technically precise definition that has a boolean-precise meaning, but it doesn't correspond terribly well to what people generally "mean" by the term. Eventually programs people think of as "iterative" will end up with cycles in the call graph simply due to sheer size, rather than the use of any recursive techniques. You'll probably find that if you try to create a precise definition of what people generally mean, you can't. Since that's my belief, I didn't try very hard. Getting too wrapped up in labels is often an impediment to understanding anyhow; what's important is that there are legitimately two distinct ways of thinking about how to code, and we aren't really that well served by insisting that they can't be labeled because they can't be precisely defined. (Well, more ways than that, of course, but we're discussing two today.)
- madez 9y ago
  I think iteration and recursion can be defined perfectly well. If people unconsciously create a more complex cycle, that might even be decomposable into distict smaller cycles, then thats still a perfectly fine recursion. A program can apply both, recursion and iteration, together to solve a problem. Maybe the problem in the conversation is that it's context is implicit and inconsistent. A recursive solution can always be written as an iterative one. Recursion is just a treat given by the language. There could be a language where any type of recursion on the language-function level is forbidden, but I doubt it would be terribly successful.
- sqeaky 9y ago
  I want to agree that languages are squishy and hard to define things. Some things are well known, but undefinable. I have yet to read a satisfactory definition of "cookie", I mean the little (except when they are big) baked good (except when they aren't baked) that are generally round (except when they aren't) and not the things web browsers store. Most definitions leave out one or more things on common grocery store shelves. I disagree that we can't strive for precision in technical discourse. Programming languages have precise meaning and are executed precisely by a machine. As an industry we are still working to define what these machine can really do to help along precise definitions can aid in communication complex topics. We could not have loops or recursion if simpler construct like conditions, jumps, gotos, variables and others did not have precise definitions. It does seem that this, how humans approach problems with these two kinds of problem decomposition, is close to the boundary of natural and machine language. This might rule it out from precise definition, but it seems to be worth a try to me.

A recursion is a cycle in the graph of function calls. Decomposing a problem into functions is something else.

by madez 9y ago

A recursion is a cycle in the graph of function calls. Decomposing a problem into functions is something else.

Indeed. That is a concise definition of recursion. But why have a cycle in a call stack (implicitly linearizing a graph) when you can replace it with a cycle in your data structure without spooky action at a distance controlled by a compiler? In an explicit representation of the "work graph" you can easily prove a finite number of walks or a cycle (and then break it in some way). Doing that directly for a nontrivial function without using graph theorems is much harder. Yes it is "easier" syntactically but then also easy to shoot yourself in the foot. Since a function call is a primitive you only get primitive tools to handle problems with it. Exceptions for example tend to unwind the stack which can take a long time. In functional languages you can end up with Bottom state from nowhere or a plain old crash.

jerf 9y ago

That's a technically precise definition that has a boolean-precise meaning, but it doesn't correspond terribly well to what people generally "mean" by the term. Eventually programs people think of as "iterative" will end up with cycles in the call graph simply due to sheer size, rather than the use of any recursive techniques. You'll probably find that if you try to create a precise definition of what people generally mean, you can't. Since that's my belief, I didn't try very hard. Getting too wrapped up in labels is often an impediment to understanding anyhow; what's important is that there are legitimately two distinct ways of thinking about how to code, and we aren't really that well served by insisting that they can't be labeled because they can't be precisely defined. (Well, more ways than that, of course, but we're discussing two today.)

madez 9y ago
I think iteration and recursion can be defined perfectly well. If people unconsciously create a more complex cycle, that might even be decomposable into distict smaller cycles, then thats still a perfectly fine recursion. A program can apply both, recursion and iteration, together to solve a problem. Maybe the problem in the conversation is that it's context is implicit and inconsistent. A recursive solution can always be written as an iterative one. Recursion is just a treat given by the language. There could be a language where any type of recursion on the language-function level is forbidden, but I doubt it would be terribly successful.
sqeaky 9y ago
I want to agree that languages are squishy and hard to define things. Some things are well known, but undefinable. I have yet to read a satisfactory definition of "cookie", I mean the little (except when they are big) baked good (except when they aren't baked) that are generally round (except when they aren't) and not the things web browsers store. Most definitions leave out one or more things on common grocery store shelves. I disagree that we can't strive for precision in technical discourse. Programming languages have precise meaning and are executed precisely by a machine. As an industry we are still working to define what these machine can really do to help along precise definitions can aid in communication complex topics. We could not have loops or recursion if simpler construct like conditions, jumps, gotos, variables and others did not have precise definitions. It does seem that this, how humans approach problems with these two kinds of problem decomposition, is close to the boundary of natural and machine language. This might rule it out from precise definition, but it seems to be worth a try to me.