3 ms·

Both iteration and recursion result in repeated operations. Either way you define the operation of going up a flight of stairs, it's going to involve going "up

by dkarl 16y ago

Both iteration and recursion result in repeated operations. Either way you define the operation of going up a flight of stairs, it's going to involve going "up" a step over and over again, so there's no way to know which way your kid was thinking just from the fact that she said "up" over and over again. In the "while" scenario, the higher-level function "up the staircase" is done once and the lower-level function "up the next step" is performed many times to accomplish it. In the recursive scenario, "up the stairs" is defined in terms of "up the stairs." Climbing the last step is "up the stairs" and it is also part of the "up the stairs" operation of climbing the last two steps, which is part of the "up the stairs" operation of climbing the last three steps. So if your kid was thinking recursively, the last "up" operation would be part of the first "up" operation and also part of every intervening "up" operation. If you asked your kid on the last step of a twelve-step staircase how many "up" she was doing, she presumably wouldn't answer "twelve;" she would answer "one." Would that be because she performed the obvious optimization of a tail-recursive function, or because she wasn't actually thinking recursively?

brlewis 16y ago
Thinking recusively doesn't necessitate a mental model of the stack. See pg's comment.
- dkarl 16y ago
  Obviously not -- recursion isn't limited to computing. However, nested meanings is inherent in recursive definitions because recursion means defining something in terms of itself. If you come up with a recursive idea that happens to be amenable to tail-call optimization, then you will be able to forget about the nesting, but that only happens through work or luck. Forgetting about the nesting is an implementation hack. Consider the classic example of the Von Neumann ordinals: 0 = {} n + 1 = n ∪ {n} 3 = 2 ∪ {2} = 1 ∪ {1} ∪ {1 ∪ {1}} etc. Or even consider the most natural definition of the factorial function, which is not tail-recursive either: f(1) = 1 f(n+1) = (n+1) * f(n) As the factorial function illustrates, the most natural recursive definition is often not tail-recursive. If you're trying to turn a recursive function into a form that can be efficiently executed as a computer program, you often have to transform the function into a form that is amenable to tail-call optimization. That's something that only programmers care about, though. Or, perhaps, programmers and babies. If you believe that people naturally conceive of recursive ideas, then what happens when their ideas aren't easily transformed to a tail-recursive form? Is that why babies cry all the time? Perhaps by the time we are small children we have learned to subconsciously discard all recursive ideas that we can't transform into a tail-recursive form? If there is a part of my brain that naturally generates tail-recursive solutions to problems but won't plague me with frustrating non-tail-recursive solutions, I would love to tap into it.

by dkarl 16y ago

brlewis 16y ago

Thinking recusively doesn't necessitate a mental model of the stack. See pg's comment.

dkarl 16y ago
Obviously not -- recursion isn't limited to computing. However, nested meanings is inherent in recursive definitions because recursion means defining something in terms of itself. If you come up with a recursive idea that happens to be amenable to tail-call optimization, then you will be able to forget about the nesting, but that only happens through work or luck. Forgetting about the nesting is an implementation hack. Consider the classic example of the Von Neumann ordinals: 0 = {} n + 1 = n ∪ {n} 3 = 2 ∪ {2} = 1 ∪ {1} ∪ {1 ∪ {1}} etc. Or even consider the most natural definition of the factorial function, which is not tail-recursive either: f(1) = 1 f(n+1) = (n+1) * f(n) As the factorial function illustrates, the most natural recursive definition is often not tail-recursive. If you're trying to turn a recursive function into a form that can be efficiently executed as a computer program, you often have to transform the function into a form that is amenable to tail-call optimization. That's something that only programmers care about, though. Or, perhaps, programmers and babies. If you believe that people naturally conceive of recursive ideas, then what happens when their ideas aren't easily transformed to a tail-recursive form? Is that why babies cry all the time? Perhaps by the time we are small children we have learned to subconsciously discard all recursive ideas that we can't transform into a tail-recursive form? If there is a part of my brain that naturally generates tail-recursive solutions to problems but won't plague me with frustrating non-tail-recursive solutions, I would love to tap into it.