My favorite recursion example is multiplication. Multiplying two numbers is inherently recursive, even though we don't typically think of it that way. (Following is expressed in base 10 for clarity, but in base 2, the multiplications by powers of 10 are of course merely shifts so they don't cost anything.)
68628933
* 26973931
=
(6862 * 3931) * 10000
+ (2697 * 8933) * 10000
+ (6862 * 2697) * 10000 * 10000
+ (8933 * 3931)
And then we notice that (6862 * 3931) can be expressed as
(68 * 31) * 100
+ (39 * 62) * 100
+ (68 * 39) * 100 * 100
+ (62 * 31)
and so on for the 3 remaining products. And then each of
these two-digit multiplications can in principle be subdivided into 4 1-digit multiplications.
The reason the algorithm is recursive is that we're really talking about polynomial multiplication, which is convolution. (Other kinds of multiplication (e.g. dot products) are not convolution and this discussion doesn't apply to them.)
The above is interesting and curious, but is it useful? Yes. Karatsuba multiplication [0] exploits this recursion and adds some clever algebra to reduce the total number of multiplication instructions needed and thus speed up bignum multiplication.
For even bigger numbers, the Schönhage–Strassen algorithm [1] goes even further and uses the Fourier transform to convert the overarching convolution operation to element-by-element (dot-product style) multiplication.
[0] https://en.wikipedia.org/wiki/Karatsuba_algorithm#Recursive_...
[1] https://en.wikipedia.org/wiki/Sch%C3%B6nhage%E2%80%93Strasse...
The reason the algorithm is recursive is that we're really talking about polynomial multiplication, which is convolution. (Other kinds of multiplication (e.g. dot products) are not convolution and this discussion doesn't apply to them.)
The above is interesting and curious, but is it useful? Yes. Karatsuba multiplication [0] exploits this recursion and adds some clever algebra to reduce the total number of multiplication instructions needed and thus speed up bignum multiplication.
For even bigger numbers, the Schönhage–Strassen algorithm [1] goes even further and uses the Fourier transform to convert the overarching convolution operation to element-by-element (dot-product style) multiplication.
[0] https://en.wikipedia.org/wiki/Karatsuba_algorithm#Recursive_...
[1] https://en.wikipedia.org/wiki/Sch%C3%B6nhage%E2%80%93Strasse...