On Thu, Jan 05, 2017 at 04:50:19AM +0000, Era Scarecrow via Digitalmars-d-learn wrote: > Well re-watched a video regarding the Ackermann function which is a > heavily recursive code which may or may not ever give a result in our > lifetimes. However relying on the power of memoize I quickly find > that when the program dies (from 5 minutes or so) nearly instantly > (and only using 9Mb of memory). > > long ack(long m, long n) { > long ans; > > if (m == 0) ans = n + 1; > else if (n==0) ans = ack(m-1, 1); > // else ans = ack(m-1, ack(m, n-1)); // original > else ans = memoize!ack(m-1, memoize!ack(m, n-1)); > > return ans; > } > > This is only due to the limited stackframe space. [...]
For heavily-recursive functions like this one, you *really* want to be revising the algorithm so that it *doesn't* recurse on the runtime stack. Keep in mind that the Ackermann function was originally conceived specifically to prove that a certain elementary class of recursive functions (called "primitive recursive" functions) cannot perform certain computations. Very roughly speaking, primitive recursive functions are "well-behaved" with regard to recursion depth; so the Ackermann function was basically *designed* to have very bad (unrestricted) recursion depth such that no primitive recursive function could possibly catch up to it. Translated to practical terms, this means that your runtime stack is pretty much guaranteed to overflow except for the most trivial values of the function. The other problem with your code, as written, is that it will quickly and easily overflow any fixed-width integer such as long here. For example, ack(4,1) == 65533, but ack(4,2) is a value that requires 65536 bits to represent (i.e., an integer that's 1 KB in size), and ack(4,3) is a value that requires ack(4,2) bits to represent, i.e., the number of bits required is a number so huge that it itself requires 1KB to represent. This far exceeds any memory capacity of any computer system in existence today, and we haven't even gotten to ack(4,4) yet. You might at least be able to get to ack(4,2) if you use BigInt instead of long (though be prepared for incredibly huge running times before the answer ever appears!), but even BigInt won't help you once you get to ack(4,3) and beyond. And don't even think about ack(5,n) for any value of n greater than 0, because those values are so ridiculously huge you need special notation just to be able to write them down at all. Because of this, your code as written most definitely does *not* compute the Ackermann function except for the smallest arguments, because once ack(m, n-1) overflows long, it can only return the answer module long.max, which will be much smaller than the actual value, so the nested recursion ack(m-1, ack(n, m-1)) actually will compute a value far smaller than what the real Ackermann function would (and it would run much faster than the real Ackermann function). Not to mention, the recursive definition of the Ackermann function is really bad for actually computing its values in a computer, because it makes a huge number of recursive calls just to compute something as simple as + and * (essentially what ack(1,n) and ack(2,n) do). In a practical implementation you'd probably want to special case these arguments to use faster, non-recursive code paths. Using memoize alleviates the problem somewhat, but it could be improved more. Nonetheless, even if you optimize said code paths, you still won't be able to get any sane results for m>4 or anything beyond the first few values for m=4. The Ackermann function is *supposed* to be computationally intractible -- that's what it was designed for. :-P T -- Do not reason with the unreasonable; you lose by definition.