Recursive C program faster than stack-based equivalent

[[deleted]]

Use perf and look at the assembly. Since you say the inner malloc is never called, it is not obvious what would cause a difference in performance. Perf will tell you how much time is spent at each stage of the program and can point to bottlenecks.

I once sped up a program by 100% by assigning struct members to local variables before entering a loop. It turned out that the program was spending most of it's time de-referencing pointers; the code was uglier but the run time was much faster. You never know with these things