3 ms·

>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 Fantas

>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.

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.