Hello my friends,
for the function Ackermann, i wrote this function in this way,actually it should work on natural numbers,means 0 oder greader. for the input numbers 2,3 it works, but for example when you enter 5,0 then
we will have stackoverflow, i don't know why, it doesn't work for all the numbers, for most of them i get stackoverflow, but just for some of them it works well.
The Ackermann recursion grows super-exponentially. If memory serves, for m > 3 it will not terminate using a standard computer/algorithm due to the recursion depth. Its Wikipedia page has a table of values that illustrates that.
Thanks,
how can i change the dedicated the memory dedicated? I searched to find a way to change the dedicated memory in eclipse,but i coudnt find anything.
David Freed wrote:how can i change the dedicated the memory dedicated? I searched to find a way to change the dedicated memory in eclipse,but i coudnt find anything.
As Ulf says, it won't help you, since recursion depth also increases exponentially (possibly even by stacked powers). Your only real solution therefore is not to use recursion at all - and BigInteger's, not longs - and even then, you're likely to be able to blow BigInteger's size limit with relatively small values - that is, if you're willing to wait.
Ackermann was discovered as proof that not all computable functions are primitive recursible, so it stands to reason that you're unlikely to be able to use POR (plain old recursion) to get it done. And the numbers involved (stacked powers of 2, if memory serves) quickly get beyond the point of comprehension, let alone storage. A BigInteger can store a Googol, but not a Googolplex; and Ackermann will quickly take you beyond that.
Perhaps something more grounded in reality might be better; or alternatively, write a program that prints out what it will need to do (or at least the first few "stacks") to calculate the value.
If you're interested in playing around with how fast recursion slows down computation, maybe start with Fibonacci numbers. The recursive implementation "only" grows exponentially, so it doesn't go out of bounds quite so quickly. But it does slow down noticeably.
The naïve version of Fibonacci runs in O(1.608ⁿ) time, so it is easy to follow with a watch. There are other versions which run in linear time and Kaldewaaij has a recursive version which runs in logarithmic complexity.
Post by:autobot
We can walk to school together. And we can both read this tiny ad:
a bit of art, as a gift, the permaculture playing cards