4 ms·
> recursive algorithms, which need by definition a stack Your vocabulary is not standard. https://www.google.com/webhp?#q=recursive+algorithm https://www.goo
by gohrt 12y ago
> recursive algorithms, which need by definition a stack
Your vocabulary is not standard.
https://www.google.com/webhp?#q=recursive+algorithm https://www.google.com/webhp?#q=recursive+algorithm
http://en.wikipedia.org/wiki/Recursion_(computer_science) 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.
- 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.)
- bad_user 12y agoIt's very standard in computer science in the theory of formal languages. https://en.wikipedia.org/wiki/Pushdown_automaton https://en.wikipedia.org/wiki/Pushdown_automaton