At a minimum, each frame of a recursively implemented algorithm in a typical AOT system without special allocations (say, milquetoast GCC 9) needs to save on each frame the return address in addition to whatever data the algorithm itself needs. Add on top of that a frame pointer, padding for stack alignment, and so on and you can end up with significant overhead you can avoid implementing the same algorithm with an explicit stack.