This however quickly results in a StackOverflowError. Instead, let's do some analysis on paper first. This is what I got:
Adding special cases for m <= 3 and memorizing results we've calculated before yields the following code:
This program finishes running almost instantly and if I comment out line 20 it prints the following results, which should give you an indication of the amount of memory it uses:
which should give you an indication of the amount of memory it uses
When we get the final results for n, is that an indication of memory use? If you have already explained it throughout the code sorry for asking about it. We had to program Ackermann for my CSC class computing the value, doing tracing like you did and also doing table look-up that stores already found values in a 2D array that way before we go into the if statements first we see if the previous recursive call is in the table already. If it is, then we can return it thus optimizing the program. But I am not that advanced yet in Java which is why I am lost in the second code you posted.
Thanks for the amazing detailed explanation. I'll get back to it when I'm ready!
For those unfamiliar with Ackerman watch this video on YouTube; Professor Brailsford explains what it is. There were certain things in the computing world that were so big that just had to be done recursively. Some people argued that they can just be done with for loops instead. Ackermann, a research student of mathematician David Hilbert was apparently the first to realize this and wondered if there actually was a problem that could only be done recursively. Very insightful video.
Daniel Andres wrote:doing table look-up that stores already found values in a 2D array
That's exactly what my program does as well. An array is a data structure that takes an integer, and returns a value associated with that integer. A two-dimensional array takes two integers and returns a value associated with the Cartesian product of those two integers. A Map also takes one value, and returns a value associated with it. Map<Integer, Map<Integer, Integer>> is really the same as int, and calling memorizeResult(m, n, result), is the same as performing array[m][n] = result. I chose Map because the size of an array needs to be known ahead of time, while a Map can grow as needed.
But I am not that advanced yet in Java which is why I am lost in the second code you posted.
Here's the same code, except in less concise form:
When we get the final results for n, is that an indication of memory use?
The results that my program print are ALL the calculations that it stored in the table in order to compute A(4,1) fast. It didn't store anything for m <= 2, because those values are calculated directly from the special cases that I added on lines 18 and 19 of the original code. If I disable those lines, the memory and time used become MUCH greater. This is not an indication of peak memory usage though, because it doesn't count stack frames. Indeed, the stack will blow up much sooner than the Map...
It's interesting that the professors in the video need so much time to calculate A(4,1), because that would mean they're not using memoization, and they have a huge stack to be able to make the recursive calls.
If I replace all Integers in my program with BigIntegers and enable the special case for (m == 3), my application is able to immediately calculate A(4,2):
You can imagine that calculating A(4,3) or A(5,1) is not going to happen...