Re:Thinking About Recursion
by dreamcompiler on Thursday March 09, 2017 @12:31AM
(#13827227)
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.
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.