4 ms·

My favourite analogy is that of finding out which row you are in at the cinema. You don't know which row you are, but you know you're 1 behind the guy in front

My favourite analogy is that of finding out which row you are in at the cinema. You don't know which row you are, but you know you're 1 behind the guy in front of you, so you ask him and figure you'll just add 1 to that. He doesn't know either, and using the same strategy he asks the person in front of him. Eventually, the guy in the second row asks the guy in the first row, who immediately says he's in the first row. Then each person adds 1 to the answer they get back and feed it back until eventually you get your answer.

charles-salvia 10y ago
That's a good analogy - the problem is a student could reasonably ask "why would you do it this way"? - i.e. this kind of algorithm seems like a better candidate for iteration. Instead of asking the guy in front of you, get up and count the rows. I know it's for teaching purposes of course, but I'd like the analogy to involve a task that requires that you try something, then back track to some earlier state, then try a different thing, etc. Of course, I guess this just highlights how all the toy examples we see in CS courses often use trivial things like computing Fibonacci sequences or factorials, which are much easier to do iteratively. This often leaves students wondering why anyone would ever even use recursion, or at best, makes it seem like recursion vs. iteration is a mere stylistic choice.
- clusmore 10y ago
  >the problem is a student could reasonably ask "why would you do it this way"? - i.e. this kind of algorithm seems like a better candidate for iteration Fantastic question. And a point I would respond with is that if you were to actually get up and walk to the front of the cinema counting rows as you go, you would realise that in doing so you would have walked forwards one row and then performed exactly the same action that the person in front of you would have done had they tried to count their row. So even this "iterative" procedure parallels recursion. Perhaps a problem that seems harder to convert to iteration is that of evaluating arbitrary arithmetic expressions. In order to evaluate a binary expression, you evaluate its two parts (recursively) and then perform the binary operator on the two operands. In order to evaluate a numeric literal, you simply take its value. So (1 + (2 * 3)) involves evaluating 1 to itself, (2 * 3) to 6, and then finally (1 + 6) to 7.
  - dreamcompiler 10y ago
    Ordinary scalar multiplication can itself be expressed recursively, e.g. (2734 * 5896). Break each number into two parts and the answer is (27 * 96 * 100) + (34 * 58 * 100) + (27 * 58 * 100 * 100) + (34 * 96). Fine. Now what is (27 * 96)? (2 * 6 * 10) + (7 * 9 * 10) + (2 * 9 * 10 * 10) + (7 * 6). etc. [In real life you'd do this in binary and the multiplies by 10 become shifts.] This is not usually the fastest way to do scalar multiplication, but it illustrates that: 1. Ordinary scalar multiplication is polynomial multiplication. 2. Polynomial multiplication is convolution. 3. And since we can [sometimes] speed up convolution by moving it to the Fourier domain, we can multiply numbers by taking their FFTs first, doing an elementwise multiplication, and then taking an inverse FFT. This actually pays off on very large numbers. Multiplication is fun stuff.
- jcranmer 10y ago
  The Ackermann function I personally find better for recursion since you can't implement it trivially with iteration--it's not primitive recursive. The downside is that it's double-recursive (which can be problematic if you're trying to teach the concept in assembly), and it's not particularly clear why such a function should exist (although one can point out that it's basically a generalization of addition/multiplication/exponentation/tetration to arbitrary degrees).

charles-salvia 10y ago

That's a good analogy - the problem is a student could reasonably ask "why would you do it this way"? - i.e. this kind of algorithm seems like a better candidate for iteration. Instead of asking the guy in front of you, get up and count the rows. I know it's for teaching purposes of course, but I'd like the analogy to involve a task that requires that you try something, then back track to some earlier state, then try a different thing, etc. Of course, I guess this just highlights how all the toy examples we see in CS courses often use trivial things like computing Fibonacci sequences or factorials, which are much easier to do iteratively. This often leaves students wondering why anyone would ever even use recursion, or at best, makes it seem like recursion vs. iteration is a mere stylistic choice.

clusmore 10y ago
>the problem is a student could reasonably ask "why would you do it this way"? - i.e. this kind of algorithm seems like a better candidate for iteration Fantastic question. And a point I would respond with is that if you were to actually get up and walk to the front of the cinema counting rows as you go, you would realise that in doing so you would have walked forwards one row and then performed exactly the same action that the person in front of you would have done had they tried to count their row. So even this "iterative" procedure parallels recursion. Perhaps a problem that seems harder to convert to iteration is that of evaluating arbitrary arithmetic expressions. In order to evaluate a binary expression, you evaluate its two parts (recursively) and then perform the binary operator on the two operands. In order to evaluate a numeric literal, you simply take its value. So (1 + (2 * 3)) involves evaluating 1 to itself, (2 * 3) to 6, and then finally (1 + 6) to 7.
- dreamcompiler 10y ago
  Ordinary scalar multiplication can itself be expressed recursively, e.g. (2734 * 5896). Break each number into two parts and the answer is (27 * 96 * 100) + (34 * 58 * 100) + (27 * 58 * 100 * 100) + (34 * 96). Fine. Now what is (27 * 96)? (2 * 6 * 10) + (7 * 9 * 10) + (2 * 9 * 10 * 10) + (7 * 6). etc. [In real life you'd do this in binary and the multiplies by 10 become shifts.] This is not usually the fastest way to do scalar multiplication, but it illustrates that: 1. Ordinary scalar multiplication is polynomial multiplication. 2. Polynomial multiplication is convolution. 3. And since we can [sometimes] speed up convolution by moving it to the Fourier domain, we can multiply numbers by taking their FFTs first, doing an elementwise multiplication, and then taking an inverse FFT. This actually pays off on very large numbers. Multiplication is fun stuff.
jcranmer 10y ago
The Ackermann function I personally find better for recursion since you can't implement it trivially with iteration--it's not primitive recursive. The downside is that it's double-recursive (which can be problematic if you're trying to teach the concept in assembly), and it's not particularly clear why such a function should exist (although one can point out that it's basically a generalization of addition/multiplication/exponentation/tetration to arbitrary degrees).