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