> An attempt at a better answer might be that a problem is “inherently” recursive. However, that’s just a limitation of viewpoint. There’s nothing more inherent

> An attempt at a better answer might be that a problem is “inherently” recursive. However, that’s just a limitation of viewpoint. There’s nothing more inherently recursive than iterative about factorial. All the problems above can be expressed even more declaratively, as in a mathematical specification, that eliminates any implementation directive (e.g.: the greatest common divisor is the greatest, common, divisor: the definition of the problem says nothing about how to find it, and searching through all numbers to find divisors that are common and taking the largest one is no less valid a solution). I always thought Euclid's algorithm had a pretty great runtime complexity, compared to "list all divisors, choose the greates common one". Is that not correct?