> (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), 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.)
It's very standard in computer science in the theory of formal languages.
Your vocabulary is not standard.
https://www.google.com/webhp?#q=recursive+algorithm
http://en.wikipedia.org/wiki/Recursion_(computer_science)
A recursive algorithm is one that computes a result by way of the same algorithm applied to a smaller input. (Smaller, or else the algorithm will diverge.)
The distinction between "stack" and "parameter" is a minor one. A simple factorial function has an ever-growing (accumulating) parameter.
Tail-recursive algorithms can be translated into loop algorithms. Thet are still recursive.