A device, system and method for securely executing recursive computations over encrypted data in a homomorphically encrypted (HE) space. For a recursive algorithm with sequentially dependent recursive iterations, executing the recursive algorithm in parallel by computing multiple recursive iterations simultaneously over multiple parallel execution iterations and not in sequential order. Each parallel execution iteration may compute a partial HE solution of multiple sequential recursive iterations comprising a known HE part and leaves empty a placeholder call slot for an unknown HE part. Placeholder call slots remain empty and are filled at delayed times at a later parallel execution iteration from when the known part of the same HE computation is computed. A final HE solution is computed in fewer multiple parallel execution iterations than the number of sequential recursive iterations, thereby accelerating the recursive algorithm in HE space.