Better performance with (Recompile) option, How?
What's probably going on is that you're running the query with different input values in your parameter. Let's look at this simplified example:

SELECT columns FROM table WHERE something=@var;


This query might return zero rows, a single row or millions of rows, depending on the value of @var. The first time you run this query (without RECOMPILE), SQL Server generates a query plan based on the value of the variable for that execution.

Suppose that value of @var returns a single row, the query can afford an execution plan that takes 0.1 seconds for each row it returns, completing your query in 0.1 seconds total. Now, if you apply that same plan to another value of @val where the query returns 1000 rows, that query is going to run for minutes and you would probably be better off with another plan, perhaps with different joins, aggregates, etc.

When you use WITH RECOMPILE, SQL Server will evaluate the query (and the variable values) every time it runs and recreate the execution plan every time. This will add a few milliseconds to each execution (to generate the plan) but the resulting plan will probably be better suited for your particular value of @val.

If you're fine with an execution time of two seconds, this won't be a problem. However, if your query needs to complete in milliseconds, I would start tuning indexes, updating statistics, etc.

In summary, yes, this sounds a lot like a parameter sniffing problem, and WITH RECOMPILE appears to be a good solution in your scenario. I can't make any more qualified guesses without looking at query plans, tables and indexes, statistics and the different parameter values. Hope that helps.