4 ms·
> (Smaller, or else the algorithm will diverge.) This is not true. The first example that comes to mind is the ridiculously over-powered one: conjecturally (
by JadeNB 12y ago
> (Smaller, or else the algorithm will diverge.)
This is not true. The first example that comes to mind is the ridiculously over-powered one: conjecturally (https://en.wikipedia.org/wiki/Collatz_conjecture https://en.wikipedia.org/wiki/Collatz_conjecture), the definition
f x | x `mod` 2 == 0 = f x/2
f x | x `mod` 2 == 1 = f $ 3*x - 1
f 1 = [ whatever ]
is perfectly well defined on positive integers `x`, although many recursive calls actually apply `f` to larger values.
(To be fair, you didn't actually say what 'smaller' meant. I think it's one of the standard term-rewriting theorems that, if given the freedom to define 'smaller' appropriately, then any total recursive function does make only smaller recursive calls.)