International Journal of Science, Engineering and TechnologyAuthors: Omar Khan Durrani, Almas Sadaf Farooqi, Harshitha Sindhe
Abstract: Asymptotic analysis of recursive algorithms usually emphasises time complexity, leaving space underexamined on managed runtimes, where realised memory cost depends on object layout and collector behaviour as well as algorithmic structure. This study uses the Tower of Hanoi (TOH), whose optimal solution comprises 2^N-1 moves, as a controlled workload for characterising spatial performance in Java. Three paradigms are formalised: (i) pure recursion, with auxiliary space bounded by call-stack depth, O(N); (ii) an iterative variant with an explicit stack, relocating the same O(N) state to the heap; and (iii) a move-materialising variant retaining the full sequence, requiring Θ(2^N) space. Analytical footprint models are derived from frame size, object-header size, reference width, and alignment padding. The models are validated using the Java Runtime API, sampling live-heap occupancy after forced collection across increasing N until resource exhaustion. Repeated trials yield mean estimates, and model fit is assessed by regression on log-transformed data. Sensitivity to heap bounds, thread stack size, and collector choice is analysed to separate algorithmic effects from runtime effects. Asymptotic space classes are preserved on the JVM, but materialisation exhausts the heap at far smaller N than recursion, while deep recursion fails through StackOverflowError. Lazy move generation is recommended.
