31–36 of 36 posts
That's a great list worthy of study in any context.
Didn't most of us get in to this mathsy line of work precisely because we didn't need to memorise a load of stuff and could just work things out from first principles as and when required?
Earlier quoted context omitted.
I was asked something like this in Amazon SE interview - find something without using loops, the answer was to use recursion. Sigh.
Isn't there an actual distinction here -- induction versus co-induction? I would argue that a loop constructs an answer, while recursion deconstructs input. There's a duality, so you can port algorithms between the two models, but there is an actual distinction.
For one thing, all loops can be trivially unrolled into a tail-recursive function that most languages will trivially transform back into a loop. Clearly these transforms have no bearing on the nature of the computation.
If asked such a question, I’d probably just use goto. (Bonus points if candidates use a goto on one part of one question I ask, since it saves a minute or two of whiteboard cut and paste, BTW).
Earlier quoted context omitted.
Isn't there an actual distinction here -- induction versus co-induction? I would argue that a loop constructs an answer, while recursion deconstructs input. There's a duality, so you can port algorithms between the two models, but there is an actual distinction.
I don’t see what recursion/loops have to do with constructing output or dividing and conquering input. For one thing, all loops can be trivially unrolled into a tail-recursive function that most languages will trivially transform back into a loop. Clearly these transforms have no bearing on the nature of the computation. If asked such a question, I’d probably just use goto. (Bonus points if candidates use a goto on o…
That there's a transform between them doesn't make them the same thing, it makes them possible to use for each other in programming. You even seem aware that there's still a distinction -- you're just not sure why it matters.
> Clearly these transforms have no bearing on the nature of the computation.
Depending on the nature of the job, not understanding why you can transform between loops and recursion is big points off. (You can go back and forth because while not the same thing, they're duals, which means you'll be able to find similar structures in both for certain classes of problems.)
That's why you need to understand what induction vs co-induction is -- so you can prove things about the transforms between them, such as that it doesn't impact the result to change the algorithm in a particular manner.
Similarly, you're only talking about really simple inductive or recursive behaviors -- what about complex cases? Are all inductive structures transformable to co-inductive (or the other direction)? What does it do to computational complexity when you make the transform?
That there's an uninteresting kernel in the transform doesn't make the entire transform trivial -- it just means you're only used to working in the "well-behaved" portion of it. (And that there is such a kernel is itself an interesting fact about computation!)
> Clearly these transforms have no bearing on the nature of the computation.
Just to reiterate how off-base I find this comment: there's entire huge collaborations in mathematics and academic computer science exploring the nature of those transforms because understanding how they can be applied is essential for moving forward with things like mechanically/formally verified software.
I get that not everyone is going to know that distinction and its impact -- but the distinction absolutely matters. As you astutely point out, it's used by compilers routinely -- and they certainly need to be sure the transform is well-behaved in the cases they apply it!
Earlier quoted context omitted.
I don’t see what recursion/loops have to do with constructing output or dividing and conquering input. For one thing, all loops can be trivially unrolled into a tail-recursive function that most languages will trivially transform back into a loop. Clearly these transforms have no bearing on the nature of the computation. If asked such a question, I’d probably just use goto. (Bonus points if candidates use a goto on o…
> For one thing, all loops can be trivially unrolled into a tail-recursive function that most languages will trivially transform back into a loop. That there's a transform between them doesn't make them the same thing, it makes them possible to use for each other in programming. You even seem aware that there's still a distinction -- you're just not sure why it matters. > Clearly these transforms have no bearing on t…
I’m not sure what you’re trying to get at...
Earlier quoted context omitted.
> For one thing, all loops can be trivially unrolled into a tail-recursive function that most languages will trivially transform back into a loop. That there's a transform between them doesn't make them the same thing, it makes them possible to use for each other in programming. You even seem aware that there's still a distinction -- you're just not sure why it matters. > Clearly these transforms have no bearing on t…
You said that recursive and iterative computations are fundamentally different. I pointed out a class of recursive and iterative algorithms that are equivalent to each other. That class disproves your statement. I’m not sure what you’re trying to get at...
Assuming you mean the and not a, they're still not the same, as equivalent algorithms need not be identical. Example: 5-3 and 1+1 both compute the result 2, making them equivalent but non-identical algorithms.
There's a way to transform any subtractive recipe for a number into an additive recipe so they're equivalent classes, but addition and subtraction aren't identical as operations.